A fast network-decomposition algorithm and its applications to constant-time distributed computation
DOI10.1016/j.tcs.2016.07.005zbMath1409.68322arXiv1505.05697OpenAlexW2487418934MaRDI QIDQ1625605
Michael Elkin, Leonid Barenboim, Cyril Gavoille
Publication date: 29 November 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1505.05697
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- Approximating \(k\)-spanner problems for \(k>2\)
- Fast distributed network decompositions and covers
- Families of finite sets in which no set is covered by the union of \(r\) others
- A note on Ramsey numbers
- Zero knowledge and the chromatic number
- Low diameter graph decompositions
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks
- Sublogarithmic distributed MIS algorithm for sparse graphs using nash-williams decomposition
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- On the locality of distributed sparse spanner construction
- Super-Fast 3-Ruling Sets.
- Improved Approximation for the Directed Spanner Problem
- On the Locality of Some NP-Complete Problems
- New and Improved Bounds for the Minimum Set Cover Problem
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
- Locality in Distributed Graph Algorithms
- Generating Sparse 2-Spanners
- The Ramsey number R(3, t) has order of magnitude t2/log t
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Distributed (δ+1)-coloring in linear (in δ) time
- Deterministic distributed vertex coloring in polylogarithmic time
- On the locality of bounded growth
- What can be computed locally?
- Distributed approximation algorithms for weighted shortest paths
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
- Directed spanners via flow-based linear programs
- Probability and Computing
- Constant-time distributed dominating set approximation
This page was built for publication: A fast network-decomposition algorithm and its applications to constant-time distributed computation
