{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:06:25Z","timestamp":1749873985476,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["I6915","P36280"],"award-info":[{"award-number":["I6915","P36280"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733547","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"88-98","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Nearly-Optimal Distributed Ruling Sets for Trees and high-girth graphs"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-3582-4880","authenticated-orcid":false,"given":"Malte","family":"Baumecker","sequence":"first","affiliation":[{"name":"Graz University of Technology, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4062-6991","authenticated-orcid":false,"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[{"name":"Graz University of Technology, Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5179-5056","authenticated-orcid":false,"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[{"name":"Aalto University, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_1_2_1","unstructured":"Anonymous. [n. d.]. personal communication."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2021.6"},{"key":"e_1_3_2_1_4_1","volume-title":"Network Decomposition and Locality in Distributed Computation. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS). 364\u2013369","author":"Awerbuch Baruch","unstructured":"Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. 1989. Network Decomposition and Locality in Distributed Computation. In the Proceedings of the Symposium on Foundations of Computer Science (FOCS). 364\u2013369."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520027"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00042"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1381770"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Malte Baumecker Yannic Maus and Jara Uitto. 2025. Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs. arXiv:2504.21777 [cs.DS] 10.48550\/arXiv.2504.21777","DOI":"10.48550\/arXiv.2504.21777"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611512"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2023.11"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2023.11"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00376-1"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365004"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2017.18"},{"key":"e_1_3_2_1_17_1","volume-title":"the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). 53\u201360","author":"Gfeller B.","unstructured":"B. Gfeller and E. Vicari. 2007. A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). 53\u201360."},{"key":"e_1_3_2_1_18_1","volume-title":"An Improved Distributed Algorithm for Maximal Independent Set. In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 270\u2013277","author":"Ghaffari Mohsen","year":"2016","unstructured":"Mohsen Ghaffari. 2016. An Improved Distributed Algorithm for Maximal Independent Set. In the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA). 270\u2013277."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00007"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch97"},{"key":"e_1_3_2_1_21_1","volume-title":"Improved Distributed Delta-Coloring. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). 427\u2013436","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. 2018. Improved Distributed Delta-Coloring. In the Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC). 427\u2013436. https:\/\/dl.acm.org\/citation.cfm?id=3212764"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2024.29"},{"key":"e_1_3_2_1_23_1","volume-title":"Proc. 48th ACM Symp. on Theory of Computing (STOC). 489\u2013498","author":"Henzinger M.","unstructured":"M. Henzinger, S. Krinninger, and D. Nanongkai. 2016. A deterministic almost-tight dis- tributed algorithm for approximating single-source shortest paths. In Proc. 48th ACM Symp. on Theory of Computing (STOC). 489\u2013498."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Kishore Kothapalli and Sriram Pemmaraju. 2012. Super-Fast 3-Ruling Sets. 136\u2013147. 10.4230\/LIPIcs.FSTTCS.2012.136","DOI":"10.4230\/LIPIcs.FSTTCS.2012.136"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01325-7_19"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993813"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461804"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583668.3594579"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.43"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538472"},{"key":"e_1_3_2_1_35_1","volume-title":"Polylogarithmic-time Deterministic Network Decomposition and Distributed Derandomization. In the Proceedings of the Annual ACM Symposium on Theory of Computing (STOC). 350\u2013363","author":"Rozho\u0148 V\u00e1clav","year":"2020","unstructured":"V\u00e1clav Rozho\u0148 and Mohsen Ghaffari. 2020. Polylogarithmic-time Deterministic Network Decomposition and Distributed Derandomization. In the Proceedings of the Annual ACM Symposium on Theory of Computing (STOC). 350\u2013363."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.004"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835760"}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732772.3733547","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:25:46Z","timestamp":1749824746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733547"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":37,"alternative-id":["10.1145\/3732772.3733547","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733547","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}