Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
From MaRDI portal
Publication:992509
DOI10.1007/S00446-009-0088-2zbMATH Open1231.68174OpenAlexW2022155283MaRDI QIDQ992509FDOQ992509
Authors: 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
Recommendations
- Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
- The locality of distributed symmetry breaking
- An Improved Distributed Algorithm for Maximal Independent Set
- Distributed Maximal Independent Set using Small Messages
- Brief announcement: Using read-\(k\) inequalities to analyze a distributed MIS algorithm
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distributed algorithms (68W15) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- Distributed Computing: A Locality-Sensitive Approach
- Decomposition of Finite Graphs Into Forests
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- What cannot be computed locally!
- Locality based graph coloring
- On the complexity of distributed graph coloring
- Distributed Computing
- Families of finite sets in which no set is covered by the union of \(r\) others
- A log-star distributed maximal independent set algorithm for growth-bounded graphs
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Symmetry breaking in distributed networks
- On the locality of bounded growth
- Graph treewidth and geometric thickness parameters
- Parallel Symmetry-Breaking in Sparse Graphs
- Deterministic coin tossing with applications to optimal parallel list ranking
- Graph minors and graphs on surfaces
- Efficient computation of implicit representations of sparse graphs
Cited In (35)
- An optimal maximal independent set algorithm for bounded-independence graphs
- Linial for lists
- Distributed independent sets in interval and segment intersection graphs
- Title not available (Why is that?)
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Distributed algorithms for random graphs
- A constructive arboricity approximation scheme
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- Distributed coloring in sparse graphs with fewer colors
- Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
- Distributed coloring and the local structure of unit-disk graphs
- Deterministic subgraph detection in broadcast CONGEST
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
- The arboricity captures the complexity of sampling edges
- Property testing of planarity in the \textsf{CONGEST} model
- Distributed coloring and the local structure of unit-disk graphs
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- Distributed MIS in O(log log n) Awake Complexity
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
- Efficient computation of sparse structures
- The communication complexity of set intersection and multiple equality testing
- Near-optimal distributed dominating set in bounded arboricity graphs
- Improved dynamic colouring of sparse graphs
- Distributed Lower Bounds for Ruling Sets
- Improved dynamic graph coloring
- Distributed dense subgraph detection and low outdegree orientation
- Local conflict coloring revisited: Linial for lists
- Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
- Distributed coloring algorithms for triangle-free graphs
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- Distributed backup placement
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- An exponential separation between randomized and deterministic complexity in the LOCAL model
This page was built for publication: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q992509)
