{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:51:24Z","timestamp":1782971484918,"version":"3.54.5"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030795269","type":"print"},{"value":"9783030795276","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79527-6_19","type":"book-chapter","created":{"date-parts":[[2021,6,19]],"date-time":"2021-06-19T11:03:43Z","timestamp":1624100623000},"page":"334-351","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Constant Round Distributed Domination on Graph Classes with Bounded Expansion"],"prefix":"10.1007","author":[{"given":"Simeon","family":"Kublenz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6347-1198","authenticated-orcid":false,"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4298-8876","authenticated-orcid":false,"given":"Alexandre","family":"Vigny","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,20]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Akhoondian Amiri, S., Ossona de Mendez, P., Rabinovich, R., Siebertz, S.: Distributed domination on graph classes of bounded expansion. In: Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, pp. 143\u2013151 (2018)","DOI":"10.1145\/3210377.3210383"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Akhoondian Amiri, S., Schmid, S., Siebertz, S.: A local constant factor MDS approximation for bounded genus graphs. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 227\u2013233 (2016)","DOI":"10.1145\/2933057.2933084"},{"key":"19_CR3","unstructured":"Amiri, S.A., Schmid, S.: Brief announcement: a log*-time local MDS approximation scheme for bounded genus graphs. In: Proceedings of DISC (2016)"},{"issue":"3","key":"19_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3326170","volume":"15","author":"SA Amiri","year":"2019","unstructured":"Amiri, S.A., Schmid, S., Siebertz, S.: Distributed dominating set approximations beyond planar graphs. ACM Trans. Algorithms (TALG) 15(3), 1\u201318 (2019)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.ipl.2017.01.011","volume":"122","author":"N Bansal","year":"2017","unstructured":"Bansal, N., Umboh, S.W.: Tight approximation bounds for dominating set on graphs of bounded arboricity. Inf. Process. Lett 122, 21\u201324 (2017)","journal-title":"Inf. Process. Lett"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2016.07.005","volume":"751","author":"L Barenboim","year":"2018","unstructured":"Barenboim, L., Elkin, M., Gavoille, C.: A fast network-decomposition algorithm and its applications to constant-time distributed computation. Theoret. Comput. Sci. 751, 2\u201323 (2018)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"19_CR7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF02570718","volume":"14","author":"H Br\u00f6nnimann","year":"1995","unstructured":"Br\u00f6nnimann, H., Goodrich, M.T.: Almost optimal set covers in finite VC-dimension. Discrete Comput. Geom. 14(4), 463\u2013479 (1995)","journal-title":"Discrete Comput. Geom."},{"key":"19_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-87779-0_6","volume-title":"Distributed Computing","author":"A Czygrinow","year":"2008","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 78\u201392. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87779-0_6"},{"key":"19_CR9","unstructured":"Czygrinow, A., Hanckowiak, M., Wawrzyniak, W., Witkowski, M.: Distributed approximation algorithms for the minimum dominating set in k_h-minor-free graphs. In: 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 624\u2013633 (2014)","DOI":"10.1145\/2591796.2591884"},{"key":"19_CR11","unstructured":"Drange, P.G., et al.: Kernelization and sparseness: the case of dominating set. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, pp. 31:1\u201331:14 (2016)"},{"issue":"3","key":"19_CR12","doi-asserted-by":"publisher","first-page":"1743","DOI":"10.1137\/18M1172508","volume":"33","author":"E Eiben","year":"2019","unstructured":"Eiben, E., Kumar, M., Mouawad, A.E., Panolan, F., Siebertz, S.: Lossy kernels for connected dominating set on sparse graphs. SIAM J. Discrete Math. 33(3), 1743\u20131771 (2019)","journal-title":"SIAM J. Discrete Math."},{"key":"19_CR13","unstructured":"Eickmeyer, K., et al.: Neighborhood complexity and kernelization for nowhere dense classes of graphs. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, 10\u201314 July 2017, Warsaw, Poland, pp. 63:1\u201363:14 (2017)"},{"issue":"2","key":"19_CR14","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.ipl.2005.03.010","volume":"95","author":"G Even","year":"2005","unstructured":"Even, G., Rawitz, D., Shahar, S.M.: Hitting sets when the VC-dimension is small. Inf. Process. Lett. 95(2), 358\u2013362 (2005)","journal-title":"Inf. Process. Lett."},{"key":"19_CR15","unstructured":"Fabianski, G., Pilipczuk, M., Siebertz, S., Torunczyk, S.: Progressive algorithms for domination and independence. In: 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, 13\u201316 March 2019, Berlin, Germany, pp. 27:1\u201327:16 (2019)"},{"issue":"1","key":"19_CR16","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1145\/357195.357200","volume":"5","author":"RG Gallager","year":"1983","unstructured":"Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Langu. Syst. (TOPLAS) 5(1), 66\u201377 (1983)","journal-title":"ACM Trans. Program. Langu. Syst. (TOPLAS)"},{"key":"19_CR17","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 174. Freeman San Francisco (1979)"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: STOC, pp. 784\u2013797. ACM (2017)","DOI":"10.1145\/3055399.3055471"},{"issue":"6","key":"19_CR19","doi-asserted-by":"publisher","first-page":"1712","DOI":"10.1137\/16M1079336","volume":"46","author":"S Har-Peled","year":"2017","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. SIAM J. Comput. 46(6), 1712\u20131744 (2017)","journal-title":"SIAM J. Comput."},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Hilke, M., Lenzen, C., Suomela, J.: Brief announcement: local approximability of minimum dominating set on planar graphs. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pp. 344\u2013346 (2014)","DOI":"10.1145\/2611462.2611504"},{"issue":"3","key":"19_CR21","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"19_CR22","doi-asserted-by":"publisher","first-page":"1294","DOI":"10.1137\/15M103618X","volume":"31","author":"M Jones","year":"2017","unstructured":"Jones, M., Lokshtanov, D., Ramanujan, M., Saurabh, S., Such\u00fd, O.: Parameterized complexity of directed Steiner tree on sparse graphs. SIAM J. Discrete Math. 31(2), 1294\u20131327 (2017)","journal-title":"SIAM J. Discrete Math."},{"key":"19_CR23","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Springer, Boston (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2","key":"19_CR24","first-page":"1","volume":"15","author":"S Kreutzer","year":"2018","unstructured":"Kreutzer, S., Rabinovich, R., Siebertz, S.: Polynomial kernels and wideness properties of nowhere dense graph classes. ACM Trans. Algorithms (TALG) 15(2), 1\u201319 (2018)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"19_CR25","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":"19_CR26","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":"19_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-540-87779-0_27","volume-title":"Distributed Computing","author":"C Lenzen","year":"2008","unstructured":"Lenzen, C., Wattenhofer, R.: Leveraging Linial\u2019s locality limit. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 394\u2013407. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-87779-0_27"},{"key":"19_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1007\/978-3-642-15763-9_48","volume-title":"Distributed Computing","author":"C Lenzen","year":"2010","unstructured":"Lenzen, C., Wattenhofer, R.: Minimum dominating set approximation in graphs of bounded arboricity. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 510\u2013524. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15763-9_48"},{"issue":"4","key":"19_CR29","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383\u2013390 (1975)","journal-title":"Discrete Math."},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Grad and classes with bounded expansion I. decompositions. Eur. J. Comb. 29(3), 760\u2013776 (2008)","DOI":"10.1016\/j.ejc.2006.07.013"},{"issue":"3","key":"19_CR31","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/j.ejc.2011.09.008","volume":"33","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O., Wood, D.R.: Characterisations and examples of graph classes with bounded expansion. Eur. J. Comb. 33(3), 350\u2013373 (2012)","journal-title":"Eur. J. Comb."},{"key":"19_CR32","doi-asserted-by":"crossref","unstructured":"Rozhon, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: STOC, pp. 350\u2013363. ACM (2020)","DOI":"10.1145\/3357713.3384298"},{"key":"19_CR33","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.ipl.2019.01.006","volume":"145","author":"S Siebertz","year":"2019","unstructured":"Siebertz, S.: Greedy domination on biclique-free graphs. Inf. Process. Lett. 145, 64\u201367 (2019)","journal-title":"Inf. Process. Lett."},{"key":"19_CR34","doi-asserted-by":"crossref","unstructured":"Wawrzyniak, W.: Brief announcement: a local approximation algorithm for MDS problem in anonymous planar networks. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pp. 406\u2013408 (2013)","DOI":"10.1145\/2484239.2484281"},{"issue":"3","key":"19_CR35","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."}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79527-6_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,19]],"date-time":"2021-06-19T11:05:23Z","timestamp":1624100723000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79527-6_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030795269","9783030795276"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79527-6_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2021.ii.uni.wroc.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"42% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}