Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
From MaRDI portal
Publication:992509
DOI10.1007/s00446-009-0088-2zbMath1231.68174OpenAlexW2022155283MaRDI QIDQ992509
Leonid Barenboim, Michael Elkin
Publication date: 9 September 2010
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-009-0088-2
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15)
Related Items (31)
Distributed independent sets in interval and segment intersection graphs ⋮ Property testing of planarity in the \textsf{CONGEST} model ⋮ Deterministic Subgraph Detection in Broadcast CONGEST. ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Distributed algorithms for random graphs ⋮ Time-optimal construction of overlay networks ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Distributed MIS in O(log log n) Awake Complexity ⋮ Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ A Constructive Arboricity Approximation Scheme ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ Improved distributed algorithms for coloring interval graphs with application to multicoloring trees ⋮ A distributed low tree-depth decomposition algorithm for bounded expansion classes ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ The Communication Complexity of Set Intersection and Multiple Equality Testing ⋮ Distributed backup placement ⋮ Distributed coloring in sparse graphs with fewer colors ⋮ Improved Dynamic Graph Coloring ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists ⋮ Distributed coloring algorithms for triangle-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Symmetry breaking in distributed networks
- Families of finite sets in which no set is covered by the union of \(r\) others
- Efficient computation of implicit representations of sparse graphs
- Graph treewidth and geometric thickness parameters
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- 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
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- On the locality of bounded growth
- On the complexity of distributed graph coloring
- Locality based graph coloring
- Distributed Computing
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- What cannot be computed locally!
- Decomposition of Finite Graphs Into Forests
This page was built for publication: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
