Name
Abstract | ||
|---|---|---|
We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with n colours, by prior work it is known that we can find a proper 3-colouring in $\\frac{1}{2} \\log^{*}n \\pm O1$ communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many n the time complexity is precisely $\\frac{1}{2} \\log^{*} n$ communication rounds. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-25258-2_4 | Colloquium on Structural Information & Communication Complexity |
Field | DocType | Volume |
Combinatorics,Graph colouring,Upper and lower bounds,Algorithm,Distributed algorithm,Time complexity,Mathematics | Journal | abs/1502.04963 |
Citations | PageRank | References |
3 | 0.41 | 45 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joel Rybicki | 1 | 78 | 9.69 |
| Jukka Suomela | 2 | 600 | 46.99 |