MIS on trees
DOI10.1145/1993806.1993813zbMATH Open1321.68482OpenAlexW2074687256MaRDI QIDQ2943380FDOQ2943380
Authors: Christoph Lenzen, Roger Wattenhofer 
Publication date: 11 September 2015
Published in: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1993806.1993813
Recommendations
- An Improved Distributed Algorithm for Maximal Independent Set
- The locality of distributed symmetry breaking
- An optimal bit complexity randomized distributed MIS algorithm
- A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
- Distributed Maximal Independent Set using Small Messages
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- Flooding time in edge-Markovian dynamic graphs
- How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
- Parsimonious flooding in dynamic graphs
- Distributed computation in dynamic networks
- Continuous consensus via common knowledge
- Reaching Agreement in the Presence of Faults
- Knowledge and common knowledge in a distributed environment
- Perfectly secure message transmission
- Programming simultaneous actions using common knowledge
- Knowledge and common knowledge in a Byzantine environment: Crash failures
- Consensus algorithms with one-bit messages
- Broadcasting in dynamic radio networks
- Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
- Fault Tolerance in Networks of Bounded Degree
- Optimal gradient clock synchronization in dynamic networks
- Almost-Everywhere Secure Computation
- Gradient clock synchronization in dynamic networks
Cited In (12)
- Efficient computation of balanced structures
- Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
- Distributed independent sets in interval and segment intersection graphs
- Brief announcement: Using read-\(k\) inequalities to analyze a distributed MIS algorithm
- The locality of distributed symmetry breaking
- Using read-\(k\) inequalities to analyze a distributed MIS algorithm
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- Optimal dynamic distributed MIS
- Distributed MIS in O(log log n) Awake Complexity
- An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
- Distributed Lower Bounds for Ruling Sets
- Distributed reconfiguration of maximal independent sets
This page was built for publication: MIS on trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943380)
