Combinatorial algorithms for distributed graph coloring

DOI10.1007/s00446-013-0203-2zbMath1291.68426OpenAlexW2751147784MaRDI QIDQ2251151

Michael Elkin, Leonid Barenboim

Publication date: 11 July 2014

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-013-0203-2

zbMATH Keywords

coloringMISset-systems

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (4)

Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Communication-Aware Local Search for Distributed Constraint Optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lifts, discrepancy and nearly optimal spectral gap
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Families of finite sets in which no set is covered by the union of \(r\) others
• Ramanujan graphs
• Eigenvalues and expanders
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Recursive construction for 3-regular expanders
• On the exponent of all pairs shortest path problem
• All pairs shortest distances for graphs with small integer length edges
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition
• Deterministic and Energy-Optimal Wireless Synchronization
• Local Computation
• Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem
• Undirected ST-connectivity in log-space
• Near-Optimal Radio Use for Wireless Network Synchronization
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Parallel Symmetry-Breaking in Sparse Graphs
• Probabilistic checking of proofs
• Locality in Distributed Graph Algorithms
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Interactive proofs and the hardness of approximating cliques
• Distributed Computing: A Locality-Sensitive Approach
• A Combinatorial Consistency Lemma with Application to Proving the PCP Theorem
• All-Pairs Almost Shortest Paths
• Some simple distributed algorithms for sparse networks
• Combinatorial PCPs with Efficient Verifiers
• Distributed (δ+1)-coloring in linear (in δ) time
• A new technique for distributed symmetry breaking
• Deterministic distributed vertex coloring in polylogarithmic time
• On the complexity of distributed graph coloring
• Locality based graph coloring
• Fast distributed construction of k-dominating sets and applications
• Faster Algorithms for All-pairs Approximate Shortest Paths in Undirected Graphs
• What cannot be computed locally!
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Computing almost shortest paths
• The PCP theorem by gap amplification

This page was built for publication: Combinatorial algorithms for distributed graph coloring