MIS on trees

DOI10.1145/1993806.1993813MaRDI QIDQ2943380zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

asymptotic analysismaximal independent setsymmetry breakingoptimal bit complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15) Distributed systems (68M14)

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

Cites work

• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• Almost-Everywhere Secure Computation
• Broadcasting in dynamic radio networks
• Consensus algorithms with one-bit messages
• Continuous consensus via common knowledge
• Distributed computation in dynamic networks
• Fault Tolerance in Networks of Bounded Degree
• Flooding time in edge-Markovian dynamic graphs
• Gradient clock synchronization in dynamic networks
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Knowledge and common knowledge in a distributed environment
• Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
• Optimal gradient clock synchronization in dynamic networks
• Parsimonious flooding in dynamic graphs
• Perfectly secure message transmission
• Programming simultaneous actions using common knowledge
• Reaching Agreement in the Presence of Faults

Cited in

(13)

• 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
• Distributed MIS in O( n) awake complexity
• 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)