Improved distributed Δ -coloring
| dc.contributor | Aalto-yliopisto | fi |
| dc.contributor | Aalto University | en |
| dc.contributor.author | Ghaffari, Mohsen | en_US |
| dc.contributor.author | Hirvonen, Juho | en_US |
| dc.contributor.author | Kuhn, Fabian | en_US |
| dc.contributor.author | Maus, Yannic | en_US |
| dc.contributor.department | Department of Computer Science | en |
| dc.contributor.groupauthor | Professorship Suomela J. | en |
| dc.contributor.organization | Swiss Federal Institute of Technology Zurich | en_US |
| dc.contributor.organization | Albert-Ludwigs-Universität Freiburg | en_US |
| dc.contributor.organization | Technion - Israel Institute of Technology | en_US |
| dc.date.accessioned | 2021-08-09T06:32:41Z | |
| dc.date.available | 2021-08-09T06:32:41Z | |
| dc.date.issued | 2021-08 | en_US |
| dc.description | Funding Information: Partly supported by ERC Grant No. 336495 (ACDC) and Ulla Tuominen Foundation. Publisher Copyright: © 2021, The Author(s). | |
| dc.description.abstract | We 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.version | Peer reviewed | en |
| dc.format.extent | 20 | |
| dc.format.extent | 239-258 | |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.citation | Ghaffari, 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-4 | en |
| dc.identifier.doi | 10.1007/s00446-021-00397-4 | en_US |
| dc.identifier.issn | 0178-2770 | |
| dc.identifier.issn | 1432-0452 | |
| dc.identifier.other | PURE UUID: 9bca122b-ff0e-4a71-9d23-878b92098e33 | en_US |
| dc.identifier.other | PURE ITEMURL: https://research.aalto.fi/en/publications/9bca122b-ff0e-4a71-9d23-878b92098e33 | en_US |
| dc.identifier.other | PURE LINK: http://www.scopus.com/inward/record.url?scp=85110386254&partnerID=8YFLogxK | en_US |
| dc.identifier.other | PURE FILEURL: https://research.aalto.fi/files/66281368/Ghaffari_ImprovedDistributedDelta_colo.pdf | en_US |
| dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/109044 | |
| dc.identifier.urn | URN:NBN:fi:aalto-202108098286 | |
| dc.language.iso | en | en |
| dc.publisher | Springer Verlag | |
| dc.relation.ispartofseries | DISTRIBUTED COMPUTING | en |
| dc.relation.ispartofseries | Volume 34, issue 4 | en |
| dc.rights | openAccess | en |
| dc.title | Improved distributed Δ -coloring | en |
| dc.type | A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä | fi |
| dc.type.version | publishedVersion |