Combinatorial Algorithms for Distributed Graph Coloring
From MaRDI portal
Publication:3095316
DOI10.1007/978-3-642-24100-0_5zbMath1350.68277OpenAlexW88867093MaRDI QIDQ3095316
Michael Elkin, Leonid Barenboim
Publication date: 28 October 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-24100-0_5
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Families of finite sets in which no set is covered by the union of \(r\) others
- Ramanujan graphs
- Eigenvalues and expanders
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition
- Undirected ST-connectivity in log-space
- 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
- Interactive proofs and the hardness of approximating cliques
- Distributed Computing: A Locality-Sensitive Approach
- 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
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem