关于最小边解析控制集的贪婪近似算法
On Greedy Approximation Algorithm for the Minimum Edge Resolving Dominating Set Problem
DOI: 10.12677/aam.2026.158350, PDF,    科研立项经费支持
作者: 杨冰倩*, 康 娜#：河北地质大学数理教学部，河北 石家庄
关键词: 控制集；边解析控制集；贪婪近似算法；Dominating Set； Edge Resolving Dominating Set； Greedy Approximation Algorithm
摘要: 关于有限、简单无向图的最小解析控制集问题是NP-难的。本文提出的最小边解析控制集是最小解析控制集的一种新变形，也是NP-难问题。对于此类问题，我们给出了一种通过构造次模势函数解决这类问题的贪婪近似算法，并证明了该算法的近似比为 1+4lnn−3ln2 ，其中 n 表示图的顶点的个数。
Abstract: The problem of finding the minimum resolving dominating set in a finite, simple undirected graph is NP-hard. As a new variant of the minimum resolving dominating set, the minimum edge resolving dominating set introduced in this paper is also an NP-hard problem. We propose a greedy approximation algorithm for solving such problems by constructing a submodular potential function, and prove that the approximation ratio of this algorithm is 1+4lnn−3ln2 , where n is the number of vertices of the graph.
文章引用：杨冰倩, 康娜. 关于最小边解析控制集的贪婪近似算法[J]. 应用数学进展, 2026, 15(8): 253-259. https://doi.org/10.12677/aam.2026.158350

参考文献

[1] Parekh, A.K. (1991) Analysis of a Greedy Heuristic for Finding Small Dominating Sets in Graphs. Information Processing Letters, 39, 237-240.
https://doi.org/10.1016/0020-0190(91)90021-9
[2] Wan, P.J., Alzoubi, K.M. and Frieder, O. (2002) Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks. Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies, New York, 23-27 June 2002, 1597-1604.
https://doi.org/10.1109/infcom.2002.1019411
[3] Kuhn, F. and Wattenhofer, R. (2005) Constant-Time Distributed Dominating Set Approximation. Distributed Computing, 17, 303-310.
https://doi.org/10.1007/s00446-004-0112-5
[4] Mira, F.Á.H., Inza, E.P., Almira, J.M.S. and Vakhania, N. (2022) A Polynomial-Time Approximation to a Minimum Dominating Set in a Graph. Theoretical Computer Science, 930, 142-156.
https://doi.org/10.1016/j.tcs.2022.07.020
[5] Casado, A., Bermudo, S., López-Sánchez, A.D. and Sánchez-Oro, J. (2023) An Iterated Greedy Algorithm for Finding the Minimum Dominating Set in Graphs. Mathematics and Computers in Simulation, 207, 41-58.
https://doi.org/10.1016/j.matcom.2022.12.018
[6] Slater, P.J. (1975) Leaves of Trees. Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Florida, 17-20 February 1975, 549-559.
[7] Kelenc, A., Tratnik, N. and Yero, I.G. (2018) Uniquely Identifying the Edges of a Graph: The Edge Metric Dimension. Discrete Applied Mathematics, 251, 204-220.
https://doi.org/10.1016/j.dam.2018.05.052
[8] Khuller, S., Raghavachari, B. and Rosenfeld, A. (1996) Landmarks in Graphs. Discrete Applied Mathematics, 70, 217-229.
https://doi.org/10.1016/0166-218x(95)00106-2
[9] Hauptmann, M., Schmied, R. and Viehmann, C. (2012) Approximation Complexity of Metric Dimension Problem. Journal of Discrete Algorithms, 14, 214-222.
https://doi.org/10.1016/j.jda.2011.12.010
[10] Huang, Y., Hou, B., Liu, W., Wu, L., Rainwater, S. and Gao, S. (2019) On Approximation Algorithm for the Edge Metric Dimension Problem. In: Lecture Notes in Computer Science, Springer, 142-148.
https://doi.org/10.1007/978-3-030-27195-4_13
[11] Monsanto, G.B. and Rara, H.M. (2021) Resolving Restrained Domination in Graphs. European Journal of Pure and Applied Mathematics, 14, 829-841.
https://doi.org/10.29020/nybg.ejpam.v14i3.3985
[12] Zhong, H. (2024) On Greedy Approximation Algorithm for the Minimum Resolving Dominating Set Problem. Journal of Combinatorial Optimization, 48, Article No. 35.
https://doi.org/10.1007/s10878-024-01229-4
[13] Wolsey, L.A. (1982) An Analysis of the Greedy Algorithm for the Submodular Set Covering Problem. Combinatorica, 2, 385-393.
https://doi.org/10.1007/bf02579435
[14] Wan, P.J., Du, D.Z., Pardalos, P., et al. (2010) Greedy Approximations for Minimum Submodular Cover with Submodular Cost. Computational Optimization and Applications, 45, 463-474.
https://doi.org/10.1007/s10589-009-9269-y
[15] Chen, W., Zhong, H., Wu, L. and Du, D. (2022) A General Greedy Approximation Algorithm for Finding Minimum Positive Influence Dominating Sets in Social Networks. Journal of Combinatorial Optimization, 44, 1-20.
https://doi.org/10.1007/s10878-021-00812-3
[16] Lovász, L. (1983) Submodular Functions and Convexity. In: Mathematical Programming: The State of the Art, Springer, 235-257.
https://doi.org/10.1007/978-3-642-68874-4_10

为你推荐