{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T01:34:27Z","timestamp":1775266467538,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T00:00:00Z","timestamp":1560729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union's Horizon 2020 research and innovation programme","award":["665778"],"award-info":[{"award-number":["665778"]}]},{"name":"National Science Centre of Poland via POLONEZ","award":["UMO-2015\/19\/P\/ST6\/03998"],"award-info":[{"award-number":["UMO-2015\/19\/P\/ST6\/03998"]}]},{"name":"European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme","award":["648527"],"award-info":[{"award-number":["648527"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>The Minimum Dominating Set (MDS) problem is a fundamental and challenging problem in distributed computing. While it is well known that minimum dominating sets cannot be well approximated locally on general graphs, in recent years there has been much progress on computing good local approximations on sparse graphs and in particular on planar graphs. In this article, we study distributed and deterministic MDS approximation algorithms for graph classes beyond planar graphs. In particular, we show that existing approximation bounds for planar graphs can be lifted to bounded genus graphs and more general graphs, which we call locally embeddable graphs, and present<\/jats:p>\n          <jats:p>(1) a local constant-time, constant-factor MDS approximation algorithm on locally embeddable graphs, and<\/jats:p>\n          <jats:p>\n            (2) a local\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            )-time (1+\u03f5)-approximation scheme for any \u03f5 &gt; 0 on graphs of bounded genus.\n          <\/jats:p>\n          <jats:p>Our main technical contribution is a new analysis of a slightly modified variant of an existing algorithm by Lenzen et al. [21]. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on direct topological arguments but on combinatorial density arguments only.<\/jats:p>","DOI":"10.1145\/3326170","type":"journal-article","created":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T12:14:26Z","timestamp":1560860066000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Distributed Dominating Set Approximations beyond Planar Graphs"],"prefix":"10.1145","volume":"15","author":[{"given":"Saeed Akhoondian","family":"Amiri","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7798-1711","authenticated-orcid":false,"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, University of Vienna, Austria"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"Uniwersytet Warszawski, Warsaw, Poland"}]}],"member":"320","published-online":{"date-parts":[[2019,6,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures. ACM, 143--151","author":"Amiri Saeed Akhoondian","year":"2018","unstructured":"Saeed Akhoondian Amiri , Patrice Ossona de Mendez , Roman Rabinovich , and Sebastian Siebertz . 2018 . Distributed domination on graph classes of bounded expansion . In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures. ACM, 143--151 . Saeed Akhoondian Amiri, Patrice Ossona de Mendez, Roman Rabinovich, and Sebastian Siebertz. 2018. Distributed domination on graph classes of bounded expansion. In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures. ACM, 143--151."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 30th International Symposium on Distributed Computing (DISC\u201916)","author":"Amiri Saeed Akhoondian","year":"2016","unstructured":"Saeed Akhoondian Amiri and Stefan Schmid . 2016 . Brief announcement: A log-time local MDS approximation scheme for bounded genus graphs . In Proceedings of the 30th International Symposium on Distributed Computing (DISC\u201916) . Springer. Saeed Akhoondian Amiri and Stefan Schmid. 2016. Brief announcement: A log-time local MDS approximation scheme for bounded genus graphs. In Proceedings of the 30th International Symposium on Distributed Computing (DISC\u201916). Springer."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916)","author":"Amiri Saeed Akhoondian","year":"2016","unstructured":"Saeed Akhoondian Amiri , Stefan Schmid , and Sebastian Siebertz . 2016 . A local constant factor MDS approximation for bounded genus graphs . In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916) . Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz. 2016. A local constant factor MDS approximation for bounded genus graphs. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201916)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/174644.174650"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.01.011"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201914)","author":"Barenboim Leonid","year":"2014","unstructured":"Leonid Barenboim , Michael Elkin , and Cyril Gavoille . 2014 . A fast network-decomposition algorithm and its applications to constant-time distributed computation . In Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201914) . 209--223. Leonid Barenboim, Michael Elkin, and Cyril Gavoille. 2014. A fast network-decomposition algorithm and its applications to constant-time distributed computation. In Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201914). 209--223."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484244"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010020"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1090372.1710974"},{"key":"e_1_2_1_14_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman , San Francisco. Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_60"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611504"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_2_1_19_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations . Springer , 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations. Springer, 85--103."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0186-z"},{"key":"e_1_2_1_22_1","series-title":"Lecture Notes in Computer Science","volume-title":"Distributed Computing","author":"Lenzen Christoph","unstructured":"Christoph Lenzen and Roger Wattenhofer . 2008. Leveraging Linial\u2019s locality limit . In Distributed Computing . Lecture Notes in Computer Science , Vol. 5218 . Springer , 394--407. Christoph Lenzen and Roger Wattenhofer. 2008. Leveraging Linial\u2019s locality limit. In Distributed Computing. Lecture Notes in Computer Science, Vol. 5218. Springer, 394--407."},{"key":"e_1_2_1_23_1","volume-title":"Distributed Computing","author":"Lenzen Christoph","unstructured":"Christoph Lenzen and Roger Wattenhofer . 2010. Minimum dominating set approximation in graphs of bounded arboricity . In Distributed Computing , vol. 6343 . Springer , 510--524. Christoph Lenzen and Roger Wattenhofer. 2010. Minimum dominating set approximation in graphs of bounded arboricity. In Distributed Computing, vol. 6343. Springer, 510--524."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"e_1_2_1_26_1","volume-title":"Graphs on Surfaces","author":"Mohar Bojan","unstructured":"Bojan Mohar and Carsten Thomassen . 2001. Graphs on Surfaces . Johns Hopkins University Press . Bojan Mohar and Carsten Thomassen. 2001. Graphs on Surfaces. Johns Hopkins University Press."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2230458"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.01.006"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431223"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484281"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.11.008"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326170","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:58Z","timestamp":1750206358000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,17]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3326170"],"URL":"https:\/\/doi.org\/10.1145\/3326170","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,17]]},"assertion":[{"value":"2019-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}