Improved distributed Δ -coloring

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorGhaffari, Mohsenen_US
dc.contributor.authorHirvonen, Juhoen_US
dc.contributor.authorKuhn, Fabianen_US
dc.contributor.authorMaus, Yannicen_US
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.groupauthorProfessorship Suomela J.en
dc.contributor.organizationSwiss Federal Institute of Technology Zurichen_US
dc.contributor.organizationAlbert-Ludwigs-Universität Freiburgen_US
dc.contributor.organizationTechnion - Israel Institute of Technologyen_US
dc.date.accessioned2021-08-09T06:32:41Z
dc.date.available2021-08-09T06:32:41Z
dc.date.issued2021-08en_US
dc.descriptionFunding Information: Partly supported by ERC Grant No. 336495 (ACDC) and Ulla Tuominen Foundation. Publisher Copyright: © 2021, The Author(s).
dc.description.abstractWe present a randomized distributed algorithm that computes a Δ -coloring in any non-complete graph with maximum degree Δ ≥ 4 in O(logΔ)+2O(loglogn) rounds, as well as a randomized algorithm that computes a Δ -coloring in O((log log n) 2) rounds when Δ ∈ [3 , O(1)]. Both these algorithms improve on an O(log 3n/ log Δ) -round algorithm of Panconesi and Srinivasan (STOC’93), which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an Ω (log log n) round lower bound of Brandt et al. (STOC’16).en
dc.description.versionPeer revieweden
dc.format.extent20
dc.format.extent239-258
dc.format.mimetypeapplication/pdfen_US
dc.identifier.citationGhaffari, M, Hirvonen, J, Kuhn, F & Maus, Y 2021, ' Improved distributed Δ -coloring ', Distributed Computing, vol. 34, no. 4, pp. 239-258 . https://doi.org/10.1007/s00446-021-00397-4en
dc.identifier.doi10.1007/s00446-021-00397-4en_US
dc.identifier.issn0178-2770
dc.identifier.issn1432-0452
dc.identifier.otherPURE UUID: 9bca122b-ff0e-4a71-9d23-878b92098e33en_US
dc.identifier.otherPURE ITEMURL: https://research.aalto.fi/en/publications/9bca122b-ff0e-4a71-9d23-878b92098e33en_US
dc.identifier.otherPURE LINK: http://www.scopus.com/inward/record.url?scp=85110386254&partnerID=8YFLogxKen_US
dc.identifier.otherPURE FILEURL: https://research.aalto.fi/files/66281368/Ghaffari_ImprovedDistributedDelta_colo.pdfen_US
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/109044
dc.identifier.urnURN:NBN:fi:aalto-202108098286
dc.language.isoenen
dc.publisherSpringer Verlag
dc.relation.ispartofseriesDISTRIBUTED COMPUTINGen
dc.relation.ispartofseriesVolume 34, issue 4en
dc.rightsopenAccessen
dc.titleImproved distributed Δ -coloringen
dc.typeA1 Alkuperäisartikkeli tieteellisessä aikakauslehdessäfi
dc.type.versionpublishedVersion
Files