Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
From MaRDI portal
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
Cites work
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- 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
- Decomposition of Finite Graphs Into Forests
- Deterministic coin tossing with applications to optimal parallel list ranking
- Distributed Computing
- Distributed Computing: A Locality-Sensitive Approach
- Efficient computation of implicit representations of sparse graphs
- Families of finite sets in which no set is covered by the union of \(r\) others
- Graph minors and graphs on surfaces
- Graph treewidth and geometric thickness parameters
- Locality based graph coloring
- Locality in Distributed Graph Algorithms
- On the complexity of distributed graph coloring
- On the locality of bounded growth
- Parallel Symmetry-Breaking in Sparse Graphs
- Symmetry breaking in distributed networks
- What cannot be computed locally!
Cited in
(35)- A constructive arboricity approximation scheme
- Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
- Efficient computation of sparse structures
- Deterministic subgraph detection in broadcast CONGEST
- Distributed coloring algorithms for triangle-free graphs
- The communication complexity of set intersection and multiple equality testing
- Distributed independent sets in interval and segment intersection graphs
- Improved dynamic graph coloring
- Near-optimal distributed dominating set in bounded arboricity graphs
- Distributed backup placement
- Improved dynamic colouring of sparse graphs
- Distributed algorithms for random graphs
- Distributed Lower Bounds for Ruling Sets
- Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications
- Distributed MIS in O(log log n) Awake Complexity
- scientific article; zbMATH DE number 7561635 (Why is no real title available?)
- Distributed algorithms, the Lovász local lemma, and descriptive combinatorics
- Distributed coloring and the local structure of unit-disk graphs
- Property testing of planarity in the \textsf{CONGEST} model
- The arboricity captures the complexity of sampling edges
- Distributed coloring in sparse graphs with fewer colors
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- An optimal maximal independent set algorithm for bounded-independence graphs
- Sublogarithmic distributed \textsc{MIS} algorithm for sparse graphs using Nash-Williams decomposition
- Linial for lists
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- Distributed minimum vertex coloring and maximum independent set in chordal graphs
- Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
- Distributed dense subgraph detection and low outdegree orientation
- Local conflict coloring revisited: Linial for lists
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- Distributed coloring and the local structure of unit-disk graphs
- Improved distributed algorithms for coloring interval graphs with application to multicoloring trees
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)
