{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:17:34Z","timestamp":1757618254731,"version":"3.44.0"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T00:00:00Z","timestamp":1748822400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T00:00:00Z","timestamp":1748822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12471287","U20A2068","12061059"],"award-info":[{"award-number":["12471287","U20A2068","12061059"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2024-03840"],"award-info":[{"award-number":["2024-03840"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12271259"],"award-info":[{"award-number":["12271259"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10878-025-01311-5","type":"journal-article","created":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T12:59:44Z","timestamp":1748869184000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation algorithms for the total dominating set problem"],"prefix":"10.1007","volume":"49","author":[{"given":"Limin","family":"Wang","sequence":"first","affiliation":[]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"given":"Yaping","family":"Mao","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3085-2701","authenticated-orcid":false,"given":"Xiaoyan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,2]]},"reference":[{"key":"1311_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2021.106206","volume":"174","author":"FN Abu-Khzam","year":"2022","unstructured":"Abu-Khzam FN (2022) An improved exact algorithm for minimum dominating set in chordal graphs. Information Processing Letters 174:106206","journal-title":"Information Processing Letters"},{"key":"1311_CR2","unstructured":"Alipour S, Futuhi E, Karimi S (2020) On distributed algorithms for minimum dominating set problem, from theory to application. arXiv preprint arXiv:2012.04883"},{"key":"1311_CR3","doi-asserted-by":"crossref","unstructured":"Alipour S, Jafari A (2020) 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, pp. 501\u2013502","DOI":"10.1145\/3350755.3400217"},{"issue":"3","key":"1311_CR4","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/j.jtbi.2004.05.009","volume":"230","author":"S Allesina","year":"2004","unstructured":"Allesina S, Bodini A (2004) Who dominates whom in the ecosystem? Energy flow bottlenecks and cascading extinctions. Journal of Theoretical Biology 230(3):351\u2013358","journal-title":"Journal of Theoretical Biology"},{"issue":"02","key":"1311_CR5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1142\/S012905410300173X","volume":"14","author":"KM Alzoubi","year":"2003","unstructured":"Alzoubi KM, Wan PJ, Frieder O (2003) Maximal independent set, weakly-connected dominating set, and induced spanners in wireless ad hoc networks. International Journal of Foundations of Computer Science 14(02):287\u2013303","journal-title":"International Journal of Foundations of Computer Science"},{"key":"1311_CR6","doi-asserted-by":"crossref","unstructured":"Awerbuch B, Goldberg AV, Luby M, Plotkin SA (1989) Network decomposition and locality in distributed computation. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pp. 364-369","DOI":"10.1109\/SFCS.1989.63504"},{"issue":"7","key":"1311_CR7","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.ipl.2014.02.002","volume":"114","author":"Y Belhoul","year":"2014","unstructured":"Belhoul Y, Yahiaoui S, Kheddouci H (2014) Efficient self-stabilizing algorithms for minimal total $$k$$-dominating sets in graphs. Information Processing Letters 114(7):339\u2013343","journal-title":"Information Processing Letters"},{"issue":"2","key":"1311_CR8","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1109\/TPDS.2013.303","volume":"26","author":"J Chen","year":"2013","unstructured":"Chen J, He K, Du R, Zheng M, Xiang Y, Yuan Q (2013) Dominating set and network coding-based routing in wireless mesh networks. IEEE Transactions on Parallel and Distributed Systems 26(2):423\u2013433","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"11","key":"1311_CR9","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"Miroslav Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk Miroslav, Chleb\u00edkov\u00e1 Janka (2008) Approximation hardness of dominating set problems in bounded degree graphs. Information and Computation 206(11):1264\u20131275","journal-title":"Information and Computation"},{"issue":"3","key":"1311_CR10","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1002\/net.3230100304","volume":"10","author":"EJ Cockayne","year":"1980","unstructured":"Cockayne EJ, Dawes RM, Hedetniemi ST (1980) Total domination in graphs. Networks 10(3):211\u2013219","journal-title":"Networks"},{"key":"1311_CR11","unstructured":"Crescenzi P, Kann V (1995) A compendium of NP optimization problems"},{"key":"1311_CR12","doi-asserted-by":"crossref","unstructured":"Das B, Bharghavan V (1997, June) Routing in ad-hoc networks using minimum connected dominating sets. In Proceedings of ICC\u201997-International Conference on Communications (Vol. 1, pp. 376-380), IEEE","DOI":"10.1109\/ICC.1997.605303"},{"issue":"4","key":"1311_CR13","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/1054916.1054931","volume":"35","author":"M Elkin","year":"2004","unstructured":"Elkin M (2004) Distributed approximation: a survey. ACM SIGACT News 35(4):40\u201357","journal-title":"ACM SIGACT News"},{"key":"1311_CR14","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1978","unstructured":"Garey MR, Johnson DS (1978) Computers and Intractability: A guide to the theory of NP-completeness. Freeman, San Francisco"},{"key":"1311_CR15","unstructured":"Goddard W, Hedetniemi ST, Jacobs DP, Srimani PK (2003, April) A self-stabilizing distributed algorithm for minimal total domination in an arbitrary system graph. In Proceedings International Parallel and Distributed Processing Symposium, IEEE"},{"issue":"4","key":"1311_CR16","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/PL00009201","volume":"20","author":"S Guha","year":"1998","unstructured":"Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374\u2013387","journal-title":"Algorithmica"},{"key":"1311_CR17","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998) Fundamentals of Domination in Graphs, Monogr. Textb. Pure Appl. Math., vol.208"},{"key":"1311_CR18","unstructured":"Haynes TW, Hedetniemi ST, Slater PJ (1998) Domination in Graphs: Advanced Topics. Chapman and Hall\/CRC Pure and Applied Mathematics Series, vol.209, Marcel Dekker, NewYork"},{"issue":"4","key":"1311_CR19","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1137\/S0895480100375831","volume":"15","author":"TW Haynes","year":"2002","unstructured":"Haynes TW, Hedetniemi SM, Hedetniemi ST, Henning MA (2002) Domination in graphs applied to electric power networks. SIAM journal on discrete mathematics 15(4):519\u2013529","journal-title":"SIAM journal on discrete mathematics"},{"issue":"4","key":"1311_CR20","doi-asserted-by":"publisher","first-page":"417","DOI":"10.2989\/16073600709486210","volume":"30","author":"MA Henning","year":"2007","unstructured":"Henning MA, Yeo A (2007) A transition from total domination in graphs to transversals in hypergraphs. Quaestiones Mathematicae 30(4):417\u2013436","journal-title":"Quaestiones Mathematicae"},{"issue":"1","key":"1311_CR21","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.disc.2007.12.044","volume":"309","author":"MA Henning","year":"2009","unstructured":"Henning MA (2009) A survey of selected recent results on total domination in graphs. Discrete Mathematics 309(1):32\u201363","journal-title":"Discrete Mathematics"},{"key":"1311_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6525-6","volume-title":"Total domination in graphs","author":"MA Henning","year":"2013","unstructured":"Henning MA, Yeo A (2013) Total domination in graphs. Springer, New York"},{"issue":"4","key":"1311_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00446-002-0078-0","volume":"15","author":"L Jia","year":"2002","unstructured":"Jia L, Rajaraman R, Suel T (2002) An efficient distributed algorithm for constructing small dominating sets. Distributed Computing 15(4):193\u2013205","journal-title":"Distributed Computing"},{"issue":"3","key":"1311_CR24","doi-asserted-by":"publisher","first-page":"388","DOI":"10.3390\/s16030388","volume":"16","author":"P Jiang","year":"2016","unstructured":"Jiang P, Liu J, Wu F, Wang J, Xue A (2016) Node deployment algorithm for underwater sensor networks based on connected dominating set. Sensors 16(3):388","journal-title":"Sensors"},{"key":"1311_CR25","doi-asserted-by":"crossref","unstructured":"Khanna Sanjeev, Motwani Rajeev, Sudan Madhu, Vazirani Umesh (1994) On syntactic versus computational views of approximability. In Proceeding of the 35th Annual Symposium on the Foundations of Computer Science, pp. 819-830","DOI":"10.1109\/SFCS.1994.365712"},{"issue":"4","key":"1311_CR26","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/s00446-004-0112-5","volume":"17","author":"F Kuhn","year":"2005","unstructured":"Kuhn F, Wattenhofer R (2005) Constant-time distributed dominating set approximation. Distributed Computing 17(4):303\u2013310","journal-title":"Distributed Computing"},{"issue":"3","key":"1311_CR27","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1137\/0605040","volume":"5","author":"R Laskar","year":"1984","unstructured":"Laskar R, Pfaff J, Hedetniemi SM, Hedetniemi ST (1984) On the algorithmic complexity of total domination. SIAM Journal on Algebraic Discrete Methods 5(3):420\u2013425","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"1311_CR28","doi-asserted-by":"crossref","unstructured":"Papademitriou, Yannakakis M (1988) Optimization, approximation and complexity classes. In Proceeding of the 20th Annual ACM Symposium on Theory of Computing, pp.229-234","DOI":"10.1145\/62212.62233"},{"issue":"24","key":"1311_CR29","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1016\/j.ipl.2012.09.002","volume":"112","author":"O Schaudt","year":"2012","unstructured":"Schaudt O, Schrader R (2012) The complexity of connected dominating sets and total dominating sets with specified induced subgraphs. Information Processing Letters 112(24):953\u2013957","journal-title":"Information Processing Letters"},{"key":"1311_CR30","doi-asserted-by":"crossref","unstructured":"Wang L, Zhang Z, Du D, Mao Y, Zhang X (2024) A Distributed Approximation Algorithm for the Total Dominating Set Problem. In: Ghosh, S., Zhang, Z. (eds) Algorithmic Aspects in Information and Management(pp. 122\u2013132). AAIM. Lecture Notes in Computer Science, vol 15179. Springer, Singapore","DOI":"10.1007\/978-981-97-7798-3_11"},{"key":"1311_CR31","doi-asserted-by":"publisher","unstructured":"Zhu J. Approximation for minimum total dominating set. In Proceedings of the 2nd International Conference on Interaction Sciences: Information Technology, Culture and Human (ICIS \u201909). Association for Computing Machinery, New York, NY, USA, 119-124. https:\/\/doi.org\/10.1145\/1655925.1655948","DOI":"10.1145\/1655925.1655948"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01311-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-025-01311-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-025-01311-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T16:38:53Z","timestamp":1757176733000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-025-01311-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,2]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["1311"],"URL":"https:\/\/doi.org\/10.1007\/s10878-025-01311-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2025,6,2]]},"assertion":[{"value":"28 April 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of the paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"90"}}