{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:48:23Z","timestamp":1782971303679,"version":"3.54.5"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030013240","type":"print"},{"value":"9783030013257","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-01325-7_19","type":"book-chapter","created":{"date-parts":[[2018,10,30]],"date-time":"2018-10-30T17:43:05Z","timestamp":1540921385000},"page":"193-208","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Deterministic Distributed Ruling Sets of Line Graphs"],"prefix":"10.1007","author":[{"given":"Fabian","family":"Kuhn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon","family":"Weidner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,10,31]]},"reference":[{"issue":"4","key":"19_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Maimon, T.: Deterministic distributed $$(\\Delta + o(\\Delta ))$$-edge-coloring, and vertex-coloring of graphs with bounded diversity. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 175\u2013184 (2017)","DOI":"10.1145\/3087801.3087812"},{"issue":"3","key":"19_CR4","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/2903137","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 20 (2016)","journal-title":"J. ACM"},{"issue":"4","key":"19_CR5","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/rsa.3240020402","volume":"2","author":"J Beck","year":"1991","unstructured":"Beck, J.: An algorithmic approach to the lov\u00e1sz local lemma. I. Random Struct. Algorithms 2(4), 343\u2013365 (1991)","journal-title":"Random Struct. Algorithms"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"Bisht, T., Kothapalli, K., Pemmaraju, S.: Brief announcement: Super-fast t-ruling sets. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 379\u2013381 (2014)","DOI":"10.1145\/2611462.2611512"},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"Chang, Y.J., Li, W., Pettie, S.: An optimal distributed $$(\\Delta + 1) $$-coloring algorithm? In: Proceedings of 50th ACM Symposium on Theory of Computing (STOC) (2018)","DOI":"10.1145\/3188745.3188964"},{"key":"19_CR8","unstructured":"Fischer, M.: Improved deterministic distributed matching via rounding. In: Proceedings of Symposium on Distributed Computing (DISC). LIPIcs, vol. 91, pp. 17:1\u201317:15 (2017)"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Fischer, M., Ghaffari, M., Kuhn, F.: Deterministic distributed edge-coloring via hypergraph maximal matching. In: Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pp. 180\u2013191 (2017)","DOI":"10.1109\/FOCS.2017.25"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 53\u201360 (2007)","DOI":"10.1145\/1281100.1281111"},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 270\u2013277 (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Harris, D.G., Kuhn, F.: On derandomizing local distributed algorithms. CoRR abs\/1711.02194 (2017)","DOI":"10.1109\/FOCS.2018.00069"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 219\u2013225 (1998)","DOI":"10.7146\/brics.v4i38.18964"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: A faster distributed algorithm for computing maximal matchings deterministically. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 219\u2013228 (1999)","DOI":"10.1145\/301308.301360"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Harris, D.G., Schneider, J., Su, H.H.: Distributed $$(\\Delta +1)$$-coloring in sublogarithmic rounds. In: Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), pp. 465\u2013478 (2016)","DOI":"10.1145\/2897518.2897533"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: Proceedings of ACM Symposium on Theory of Computing (STOC), pp. 489\u2013498 (2016)","DOI":"10.1145\/2897518.2897638"},{"issue":"2","key":"19_CR17","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","volume":"22","author":"A Israeli","year":"1986","unstructured":"Israeli, A., Itai, A.: A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett. 22(2), 77\u201380 (1986)","journal-title":"Inf. Process. Lett."},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Izumi, T., Le Gall, F.: Triangle finding and listing in CONGEST networks. In: PODC, pp. 381\u2013389 (2017)","DOI":"10.1145\/3087801.3087811"},{"key":"19_CR19","unstructured":"Kothapalli, K., Pemmaraju, S.V.: Super-fast 3-ruling sets. In: FSTTCS. LIPIcs, vol. 18, pp. 136\u2013147 (2012)"},{"issue":"2","key":"19_CR20","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/2742012","volume":"63","author":"F Kuhn","year":"2016","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: lower and upper bounds. J. ACM 63(2), 17:1\u201317:44 (2016)","journal-title":"J. ACM"},{"key":"19_CR21","first-page":"273","volume-title":"Lecture Notes in Computer Science","author":"Fabian Kuhn","year":"2005","unstructured":"Kuhn, F., Moscriboda, T., Nieberg, T., Wattenhofer, R.: Fast deterministic distributed maximal independent set computation on growth-bounded graphs. In: Proceedings of the 19th International Conference on Distributed Computing (DISC), pp. 273\u2013287 (2005)"},{"key":"19_CR22","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Maus, Y., Weidner, S.: Deterministic distributed ruling sets of line graphs (2018)","DOI":"10.1007\/978-3-030-01325-7_19"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"Linial, N.: Distributive graph algorithms global solutions from local data. In: Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS), pp. 331\u2013335 (1987)","DOI":"10.1109\/SFCS.1987.20"},{"issue":"1","key":"19_CR24","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":"4","key":"19_CR25","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"19_CR26","unstructured":"Pai, S., Pandurangan, G., Pemmaraju, S.V., Riaz, T., Robinson, P.: Symmetry breaking in the congest model: time- and message-efficient algorithms for ruling sets. In: Proceedings of Symposium on Distributed Computing (DISC). LIPIcs, vol. 91, pp. 38:1\u201338:16 (2017)"},{"issue":"2","key":"19_CR27","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/PL00008932","volume":"14","author":"A Panconesi","year":"2001","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97\u2013100 (2001)","journal-title":"Distrib. Comput."},{"issue":"2","key":"19_CR28","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01200759","volume":"15","author":"A Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: The local nature of $$\\Delta $$-coloring and its algorithmic applications. Combinatorica 15(2), 255\u2013280 (1995)","journal-title":"Combinatorica"},{"issue":"2","key":"19_CR29","first-page":"581","volume":"20","author":"A Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 581\u2013592 (1995)","journal-title":"J. Algorithms"},{"key":"19_CR30","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality sensitive approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"19_CR31","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2012.09.004","volume":"509","author":"J Schneider","year":"2013","unstructured":"Schneider, J., Elkin, M., Wattenhofer, R.: Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci. 509, 40\u201350 (2013)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-01325-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,4]],"date-time":"2022-09-04T23:00:42Z","timestamp":1662332442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-01325-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030013240","9783030013257"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-01325-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"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":"Ma'ale HaHamisha","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Israel","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 June 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/sirocco2018","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"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"47","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"23","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"49% - 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"}},{"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"}},{"value":"1.97","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}