Exact bounds for distributed graph colouring

DOI10.1007/978-3-319-25258-2_4MaRDI QIDQ3460706zbMATH OpenOpenAlexFDO

Authors Joel Rybicki, Jukka Suomela

Publication date 8 January 2016

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.04963

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)

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 $frac12lo{g}^{\ast }(n)pmO(1)$ communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many $n$ the time complexity is precisely $frac12lo{g}^{\ast }n$ communication rounds.

Recommendations

• On the complexity of distributed graph coloring
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Improved distributed \(\Delta\)-coloring
• Improved distributed delta-coloring
• Distributed graph coloring in a few rounds

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed algorithms for \textsc{Edge Dominating Sets}
• Fast Distributed Approximations in Planar Graphs
• Improved distributed Steiner forest construction
• Locality based graph coloring
• Locality in Distributed Graph Algorithms
• On the complexity of distributed graph coloring
• Parallel Symmetry-Breaking in Sparse Graphs
• What Can be Computed Locally?

Cited in

(11)

• Distributed deterministic edge coloring using bounded neighborhood independence
• Vertex coloring with communication and local memory constraints in synchronous broadcast networks
• Distributed algorithms for the Lovász local lemma and graph coloring
• Mathematical modeling of positive connection functioning in the tumor markers p53-microRNA system
• Polynomial lower bound for distributed graph coloring in a weak LOCAL model
• Distributed Coloring in Sparse Graphs with Fewer Colors
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed minimum vertex coloring and maximum independent set in chordal graphs
• Distributed computing in the asynchronous LOCAL model
• Large cuts with local algorithms on triangle-free graphs
• Deterministic distributed vertex coloring in polylogarithmic time

This page was built for publication: Exact bounds for distributed graph colouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460706)