Exact Bounds for Distributed Graph Colouring

DOI10.1007/978-3-319-25258-2_4zbMath1471.68323arXiv1502.04963OpenAlexW1752989563MaRDI QIDQ3460706

Jukka Suomela, Joel Rybicki

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)

Related Items (2)

Mathematical modeling of positive connection functioning in the tumor markers p53-microRNA system ⋮ Large cuts with local algorithms on triangle-free graphs

Cites Work

• Unnamed Item
• Improved distributed steiner forest construction
• Fast Distributed Approximations in Planar Graphs
• Deterministic coin tossing with applications to optimal parallel list ranking
• Parallel Symmetry-Breaking in Sparse Graphs
• A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
• Locality in Distributed Graph Algorithms
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• What Can be Computed Locally?
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Distributed algorithms for edge dominating sets
• On the complexity of distributed graph coloring
• Locality based graph coloring
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring

This page was built for publication: Exact Bounds for Distributed Graph Colouring