{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T17:34:13Z","timestamp":1772645653560,"version":"3.50.1"},"reference-count":40,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T00:00:00Z","timestamp":1684800000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"publisher","award":["62272215"],"award-info":[{"award-number":["62272215"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Axioms"],"abstract":"<jats:p>In this paper, we consider a variant of dominating set problem, i.e., the total dominating set problem. Given an undirected graph G=(V,E), a subset of vertices T\u2286V is called a total dominating set if every vertex in V is adjacent to at least one vertex in T. Based on LP relaxation techniques, this paper gives a distributed approximation algorithm for the total dominating set problem in general graphs. The presented algorithm obtains a fractional total dominating set that is, at most, k(1+\u03941k)\u03941k times the size of the optimal solution to this problem, where k is a positive integer and \u0394 is the maximum degree of G. The running time of this algorithm is constant communication rounds under the assumption of a synchronous communication model.<\/jats:p>","DOI":"10.3390\/axioms12060506","type":"journal-article","created":{"date-parts":[[2023,5,23]],"date-time":"2023-05-23T08:14:28Z","timestamp":1684829668000},"page":"506","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An Approximation Algorithm for a Variant of Dominating Set Problem"],"prefix":"10.3390","volume":"12","author":[{"given":"Limin","family":"Wang","sequence":"first","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenqi","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing 210023, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,5,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Jiang, P., Liu, J., Wu, F., Wang, J., and Xue, A. (2016). Node deployment algorithm for underwater sensor networks based on connected dominating set. Sensors, 16.","DOI":"10.3390\/s16030388"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1109\/TPDS.2013.303","article-title":"Dominating set and network coding-based routing in wireless mesh networks","volume":"26","author":"Chen","year":"2013","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_3","first-page":"9","article-title":"Combinatorially based cryptography for children (and adults)","volume":"99","author":"Fellows","year":"1994","journal-title":"Congr. Numer."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Kwon, S., Kang, J.S., and Yeom, Y. (2021, January 23\u201325). Analysis of public-key cryptography using a 3-regular graph with a perfect dominating set. Proceedings of the IEEE Region 10 Symposium (TENSYMP), Grand Hyatt Jeju, Republic of Korea.","DOI":"10.1109\/TENSYMP52854.2021.9550868"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1016\/j.jtbi.2004.05.009","article-title":"Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions","volume":"230","author":"Allesina","year":"2004","journal-title":"J. Theor. Biol."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1137\/S0895480100375831","article-title":"Domination in graphs applied to electric power networks","volume":"15","author":"Haynes","year":"2002","journal-title":"SIAM J. Discret. Math."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S., and Slater, P. (2013). Fundamentals of Domination in Graphs, CRC Press.","DOI":"10.1201\/9781482246582"},{"key":"ref_8","unstructured":"Haynes, T.W. (2017). Domination in Graphs: Volume 2: Advanced Topics, Routledge."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S., and Henning, M.A. (2020). Topics in Domination in Graphs, Springer Nature.","DOI":"10.1007\/978-3-030-51117-3"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S., and Henning, M.A. (2021). Structures of Domination in Graphs, Springer.","DOI":"10.1007\/978-3-030-58892-2"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1142\/S012905410300173X","article-title":"Maximal independent set, weakly-connected dominating set, and induced spanners in wireless ad hoc networks","volume":"14","author":"Alzoubi","year":"2003","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_12","unstructured":"Das, B., and Bharghavan, V. (1997, January 8\u201312). Routing in ad-hoc networks using minimum connected dominating sets. Proceedings of the ICC\u201997-International Conference on Communications, Montreal, QC, Canada."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.ipl.2014.02.002","article-title":"Efficient self-stabilizing algorithms for minimal total k-dominating sets in graphs","volume":"114","author":"Belhoul","year":"2014","journal-title":"Inf. Process. Lett."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1002\/net.3230100304","article-title":"Total domination in graphs","volume":"10","author":"Cockayne","year":"1980","journal-title":"Networks"},{"key":"ref_15","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., and Plotkin, S.A. (November, January 30). Network decomposition and locality in distributed computation. Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA."},{"key":"ref_16","unstructured":"Alipour, S., Futuhi, E., and Karimi, S. (2020). On distributed algorithms for minimum dominating set problem, from theory to application. arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Alipour, S., and Jafari, A. (2020, January 15\u201317). A local constant approximation factor algorithm for minimum dominating set of certain planar graphs. Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual.","DOI":"10.1145\/3350755.3400217"},{"key":"ref_18","unstructured":"Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998). Fundamentals of Domination in Graphs, Chapman and Hall\/CRC."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Haynes, T.W., Hedetniemi, S.T., and Slater, P.J. (1998). Domination in Graphs: Advanced Topics, Marcel Dekker.","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.disc.2007.12.044","article-title":"A survey of selected recent results on total domination in graphs","volume":"309","author":"Henning","year":"2009","journal-title":"Discret. Math."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Henning, M.A., and Yeo, A. (2013). Total Domination in Graphs, Springer.","DOI":"10.1007\/978-1-4614-6525-6"},{"key":"ref_22","unstructured":"Garey, M.R., and Johnson, D.S. (1978). Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/S0097539795286612","article-title":"On syntactic versus computational views of approximability","volume":"28","author":"Khanna","year":"1998","journal-title":"SIAM J. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Papademitriou, C., and Yannakakis, M. (1988, January 2\u20134). Optimization, approximation and complexity classes. In Proceeding of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA.","DOI":"10.1145\/62212.62233"},{"key":"ref_25","unstructured":"Crescenzi, P., and Kann, V. (1995). A Compendium of NP Optimization Problems, Department of Computer Science, University of Rome \u201cLa Sapienza\u201d. Technical Report SI\/RR-95\/02."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1137\/0605040","article-title":"On the algorithmic complexity of total domination","volume":"5","author":"Laskar","year":"1984","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"417","DOI":"10.2989\/16073600709486210","article-title":"A transition from total domination in graphs to transversals in hypergraphs","volume":"30","author":"Henning","year":"2007","journal-title":"Quaest. Math."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","article-title":"Approximation hardness of dominating set problems in bounded degree graphs","volume":"206","year":"2008","journal-title":"Inf. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Zhu, J. (2009, January 24\u201326). Approximation for minimum total dominating set. Proceedings of the 2nd International Conference on Interaction Sciences: Information Technology, Culture and Human, Seoul, Republic of Korea.","DOI":"10.1145\/1655925.1655948"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1016\/j.ipl.2012.09.002","article-title":"The complexity of connected dominating sets and total dominating sets with specified induced subgraphs","volume":"112","author":"Schaudt","year":"2012","journal-title":"Inf. Process. Lett."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Yuan, F., Li, C., Gao, X., Yin, M., and Wang, Y. (2019). A novel hybrid algorithm for minimum total dominating set problem. Mathematics, 7.","DOI":"10.3390\/math7030222"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1701","DOI":"10.3906\/mat-2001-58","article-title":"An algorithm to check the equality of total domination number and double of domination number in graphs","volume":"44","author":"Bahadir","year":"2020","journal-title":"Turk. J. Math."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"8753","DOI":"10.1007\/s10489-021-02305-6","article-title":"Towards efficient local search for the minimum total dominating set problem","volume":"51","author":"Hu","year":"2021","journal-title":"Appl. Intell."},{"key":"ref_34","unstructured":"Jena, S.K., and Das, G.K. (2021, January 10\u201312). Total domination in geometric unit disk graphs. In Proceeding of the 33rd Canadian Conference on Computational Geometry (CCCG), Halifax, NS, Canada."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","article-title":"Approximation schemes for covering and packing problems in image processing and VLSI","volume":"32","author":"Hochbaum","year":"1985","journal-title":"J. ACM (JACM)"},{"key":"ref_36","unstructured":"Goddard, W., Hedetniemi, S.T., Jacobs, D.P., and Srimani, P.K. (2003, January 22\u201326). A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph. Proceedings of the International Parallel and Distributed Processing Symposium, Nice, France."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1145\/1054916.1054931","article-title":"Distributed approximation: A survey","volume":"35","author":"Elkin","year":"2004","journal-title":"ACM SIGACT News"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s00446-004-0112-5","article-title":"Constant-time distributed dominating set approximation","volume":"17","author":"Kuhn","year":"2005","journal-title":"Distrib. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s00446-002-0078-0","article-title":"An efficient distributed algorithm for constructing small dominating sets","volume":"15","author":"Jia","year":"2002","journal-title":"Distrib. Comput."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/PL00009201","article-title":"Approximation algorithms for connected dominating sets","volume":"20","author":"Guha","year":"1998","journal-title":"Algorithmica"}],"container-title":["Axioms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2075-1680\/12\/6\/506\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T19:40:20Z","timestamp":1760125220000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2075-1680\/12\/6\/506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,23]]},"references-count":40,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,6]]}},"alternative-id":["axioms12060506"],"URL":"https:\/\/doi.org\/10.3390\/axioms12060506","relation":{},"ISSN":["2075-1680"],"issn-type":[{"value":"2075-1680","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,23]]}}}