{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T09:40:49Z","timestamp":1743154849875,"version":"3.40.3"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031744976"},{"type":"electronic","value":"9783031744983"}],"license":[{"start":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T00:00:00Z","timestamp":1729382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-74498-3_20","type":"book-chapter","created":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T11:02:30Z","timestamp":1729335750000},"page":"277-291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Tight Bounds for\u00a0Constant-Round Domination on\u00a0Graphs of\u00a0High Girth and\u00a0Low Expansion"],"prefix":"10.1007","author":[{"given":"Christoph","family":"Lenzen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sophie","family":"Wenning","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,20]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Amiri, S.A., Schmid, S., Siebertz, S.: Distributed dominating set approximations beyond planar graphs. ACM Trans. Algorith. 15(3), 39:1\u201339:18 (2019)","DOI":"10.1145\/3326170"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Amiri, S.A., Wiederhake, B.: Distributed distance-r covering problems on sparse high-girth graphs. Theor. Comput. Sci. 906, 18\u201331 (2022)","DOI":"10.1016\/j.tcs.2022.01.001"},{"key":"20_CR3","unstructured":"Bonamy, M., Cook, L., Groenland, C., Wesolek, A.: A tight local algorithm for the minimum dominating set problem in outerplanar graphs. In: 35th international symposium on distributed computing, DISC 2021, 4\u20138 Oct 2021, Freiburg, Germany (Virtual Conference). LIPIcs, vol. 209, pp. 13:1\u201313:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986)","journal-title":"Inf. Control"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Coupette, C., Lenzen, C.: A Breezing Proof of the KMW Bound. CoRR, abs\/2002.06005 (2020)","DOI":"10.1137\/1.9781611976496.21"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Czygrinow, A., Hanckowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Taubenfeld, G. (ed.) Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, 22\u201324 Sept 2008. Proceedings. Lecture Notes in Computer Science, pp. 78\u201392. Springer (2008)","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"20_CR7","unstructured":"Czygrinow, A., Hanckowiak, M., Wawrzyniak, W., Witkowski, M.: Distributed approximation algorithms for the minimum dominating set in K_h-Minor-Free graphs. In: Hsu, W.-L., Lee, D.-T., Liao, C.-S. (eds.) 29th International Symposium on Algorithms and Computation, ISAAC 2018, 16\u201319 Dec 2018, Jiaoxi, Yilan, Taiwan. LIPIcs, vol. 123, pp. 22:1\u201322:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"20_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2018.07.008","volume":"757","author":"A Czygrinow","year":"2019","unstructured":"Czygrinow, A., Hanckowiak, M., Wawrzyniak, W., Witkowski, M.: Distributed CONGESTBC constant approximation of MDS in bounded genus graphs. Theor. Comput. Sci. 757, 1\u201310 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR9","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2022.03.001","volume":"916","author":"A Czygrinow","year":"2022","unstructured":"Czygrinow, A., Hanckowiak, M., Witkowski, M.: Distributed distance domination in graphs with no K_{2, t}-minor. Theor. Comput. Sci. 916, 22\u201330 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"20_CR10","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 \u2013 June 03, 2014, pp. 624\u2013633. ACM (2014)"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Dory, M., Ghaffari, M., Ilchi, S.: Near-optimal distributed dominating set in bounded arboricity graphs. In: Milani, A., Woelfel, P. (eds.) PODC \u201922: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25\u201329, 2022, pp. 292\u2013300. ACM (2022)","DOI":"10.1145\/3519270.3538437"},{"key":"20_CR12","unstructured":"Erd\u00f6s, P., Sachs, H.: Eine Absch\u00e4tzung f\u00fcr die minimale Knotenzahl regul\u00e4rer Graphen, welche keinen Kreis der L\u00e4nge $$<$$l enthalten. Wiss. Z. Univ. Halle XII(3), 251\u2013258 (1963)"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"G\u00f6\u00f6s, M., Hirvonen, J., Suomela, J.: Lower bounds for local approximation. J. ACM 60(5), 39:1\u201339:23 (2013)","DOI":"10.1145\/2528405"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Hilke, M., Lenzen, C., Suomela, J.: Brief announcement: local approximability of minimum dominating set on planar graphs. In: Halld\u00f3rsson, M.M., Dolev, S. (eds.) ACM Symposium on Principles of Distributed Computing, PODC \u201914, Paris, France, 15\u201318 July 2014, pp. 344\u2013346. ACM (2014)","DOI":"10.1145\/2611462.2611504"},{"key":"20_CR15","doi-asserted-by":"crossref","unstructured":"Kublenz, S., Siebertz, S., Vigny, A.: Constant round distributed domination on graph classes with bounded expansion. In: Jurdzinski, T., Schmid, S. (eds.) Structural Information and Communication Complexity\u201428th International Colloquium, SIROCCO 2021, Wroc\u0142aw, Poland, June 28\u2013July 1, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12810, pp. 334\u2013351. Springer (2021)","DOI":"10.1007\/978-3-030-79527-6_19"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63(2), 17:1\u201317:44 (2016)","DOI":"10.1145\/2742012"},{"issue":"2","key":"20_CR17","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00446-013-0186-z","volume":"26","author":"C Lenzen","year":"2013","unstructured":"Lenzen, C., Pignolet, Y.-A., Wattenhofer, R.: Distributed minimum dominating set approximations in restricted families of graphs. Distrib. Comput. 26(2), 119\u2013137 (2013)","journal-title":"Distrib. Comput."},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Wenning, S.: Tight Bounds for Constant-Round Domination on Graphs of High Girth and Low Expansion (2024). https:\/\/arxiv.org\/abs\/2408.12998","DOI":"10.1007\/978-3-031-74498-3_20"},{"issue":"1","key":"20_CR19","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"20_CR20","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.ipl.2013.11.008","volume":"114","author":"W Wawrzyniak","year":"2014","unstructured":"Wawrzyniak, W.: A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs. Inf. Process. Lett. 114(3), 94\u201398 (2014)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"20_CR21","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s00446-015-0247-6","volume":"28","author":"W Wawrzyniak","year":"2015","unstructured":"Wawrzyniak, W.: A local approximation algorithm for minimum dominating set problem in anonymous planar networks. Distrib. Comput. 28(5), 321\u2013331 (2015)","journal-title":"Distrib. Comput."},{"key":"20_CR22","unstructured":"Wiederhake, B.: Pulse propagation, graph cover, and packet forwarding. PhD thesis, Saarland University, Saarbr\u00fccken, Germany (2022)"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-74498-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T22:03:46Z","timestamp":1735596226000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-74498-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,20]]},"ISBN":["9783031744976","9783031744983"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-74498-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,10,20]]},"assertion":[{"value":"20 October 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SSS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Stabilizing, Safety, and Security of Distributed Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nagoya","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Japan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 October 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 October 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sss2024.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}