{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T10:28:05Z","timestamp":1790418485493,"version":"4.1.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"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 Program","award":["755839"],"award-info":[{"award-number":["755839"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,16]]},"DOI":"10.1145\/3293611.3331626","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T09:17:21Z","timestamp":1563527841000},"page":"94-103","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Deterministic Distributed Dominating Set Approximation in the CONGEST Model"],"prefix":"10.1145","author":[{"given":"Janosch","family":"Deurer","sequence":"first","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Noga Alon and Joel H Spencer. 2004. The probabilistic method. John Wiley & Sons.  Noga Alon and Joel H Spencer. 2004. The probabilistic method. John Wiley & Sons."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63504"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Leonid Barenboim and Michael Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers.   Leonid Barenboim and Michael Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212769"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1255378.1255381"},{"key":"e_1_3_2_1_7_1","volume-title":"Proc. 31st Symp. on Distributed Computing (DISC). 11:1--11:16","author":"Censor-Hillel Keren","year":"2017"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Janosch Deurer Fabian Kuhn and Yannic Maus. 2019. Deterministic Distributed Dominating Set Approximation in the CONGEST Model. (2019).  Janosch Deurer Fabian Kuhn and Yannic Maus. 2019. Deterministic Distributed Dominating Set Approximation in the CONGEST Model. (2019).","DOI":"10.1145\/3293611.3331626"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.04.002"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms 1st ed.). Cambridge University Press New York NY USA.   Devdatt P. Dubhashi and Alessandro Panconesi. 2009. Concentration of Measure for the Analysis of Randomized Algorithms 1st ed.). Cambridge University Press New York NY USA.","DOI":"10.1017\/CBO9780511581274"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_41"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310485"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_1_15_1","volume-title":"Proc. 32nd Symp. on Distributed Computing (DISC). 29:1--29:17","author":"Ghaffari Mohsen","year":"2018"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_17_1","unstructured":"Mohsen Ghaffari and Julian Portmann. 2019. personal communication.  Mohsen Ghaffari and Julian Portmann. 2019. personal communication."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009201"},{"key":"e_1_3_2_1_19_1","unstructured":"David G. Harris. 2018. Distributed approximation algorithms for maximum matching in graphs and hypergraphs. CoRR Vol. abs\/1807.07645 (2018). http:\/\/arxiv.org\/abs\/1807.07645  David G. Harris. 2018. Distributed approximation algorithms for maximum matching in graphs and hypergraphs. CoRR Vol. abs\/1807.07645 (2018). http:\/\/arxiv.org\/abs\/1807.07645"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897638"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/777474.777476"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"e_1_3_2_1_23_1","unstructured":"David S. Johnson and Michael R Garey. 1979. Computers and Intractability A Guide to the Theory of NP-Completeness.W. H. Freeman and Company.   David S. Johnson and Michael R Garey. 1979. Computers and Intractability A Guide to the Theory of NP-Completeness.W. H. Freeman and Company."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_25_1","volume-title":"Proc. 32nd Symp. on Distributed Computing (DISC). 35:1--35:17","author":"Gregory Schwartzman Kawarabayashi","year":"2018"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109666"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-004-0112-5"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0186-z"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_27"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_3_2_1_33_1","unstructured":"Yannic Maus. 2018. The power of locality: exploring the limits of randomness in distributed computing. Ph.D. Dissertation. University of Freiburg Freiburg im Breisgau Germany. https:\/\/freidok.uni-freiburg.de\/data\/16780  Yannic Maus. 2018. The power of locality: exploring the limits of randomness in distributed computing. Ph.D. Dissertation. University of Freiburg Freiburg im Breisgau Germany. https:\/\/freidok.uni-freiburg.de\/data\/16780"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_3_2_1_35_1","first-page":"1","article-title":"(Delta 1) Coloring in the Congested Clique Model. In Proc. 45th","volume":"160","author":"Parter Merav","year":"2018","journal-title":"Int. Coll. on Automata, Languages, and Programming (ICALP)."},{"key":"e_1_3_2_1_36_1","volume-title":"Proc. 32nd Symp. on Distributed Computing (DISC). 40:1--40:18","author":"Parter Merav","year":"2018"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0091-7"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"}],"event":{"name":"PODC '19: ACM Symposium on Principles of Distributed Computing","location":"Toronto ON Canada","acronym":"PODC '19","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331626","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331626","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:02:02Z","timestamp":1750194122000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331626"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":39,"alternative-id":["10.1145\/3293611.3331626","10.1145\/3293611"],"URL":"https:\/\/doi.org\/10.1145\/3293611.3331626","relation":{},"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}