An Improved Distributed Algorithm for Maximal Independent Set

DOI10.1137/1.9781611974331.ch20zbMath1411.68175arXiv1506.05093OpenAlexW2953390354MaRDI QIDQ4575597

Mohsen Ghaffari

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.05093

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed algorithms (68W15)

Related Items (40)

Distributed independent sets in interval and segment intersection graphs ⋮ New techniques and tighter bounds for local computation algorithms ⋮ Can we locally compute sparse connected subgraphs? ⋮ Distributed reconfiguration of maximal independent sets ⋮ Graph reconstruction in the congested clique ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ What can be sampled locally? ⋮ Improved deterministic distributed matching via rounding ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Node and edge averaged complexities of local graph problems ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Time-optimal construction of overlay networks ⋮ Component stability in low-space massively parallel computation ⋮ Exact distributed sampling ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Unnamed Item ⋮ Distributed coloring of hypergraphs ⋮ Computing large independent sets in a single round ⋮ Distributed MIS in O(log log n) Awake Complexity ⋮ Distributed MIS with Low Energy and Time Complexities ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization ⋮ Optimal Message-Passing with Noisy Beeps ⋮ Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Improved distributed \(\Delta\)-coloring ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ Dynamic networks of finite state machines ⋮ A topological perspective on distributed network algorithms ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ Congested Clique Algorithms for Graph Spanners ⋮ Distributed Lower Bounds for Ruling Sets

This page was built for publication: An Improved Distributed Algorithm for Maximal Independent Set