A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation

DOI10.1007/978-3-319-25258-2_15zbMath1409.68321OpenAlexW2137594557MaRDI QIDQ3460717

Leonid Barenboim, Cyril Gavoille, Michael Elkin

Publication date: 8 January 2016

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

Full work available at URL: https://doi.org/10.1007/978-3-319-25258-2_15

Mathematics Subject Classification ID

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 (10)

A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Distributed strong diameter network decomposition ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Computing large independent sets in a single round ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set

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
• 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
• The Locality of Distributed Symmetry Breaking
• A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation
• Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Parallel Symmetry-Breaking in Sparse Graphs
• Locality in Distributed Graph Algorithms
• Generating Sparse 2-Spanners
• The Ramsey number R(3, t) has order of magnitude t²/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