Fully dynamic MIS in uniformly sparse graphs
From MaRDI portal
Publication:5002774
DOI10.4230/LIPIcs.ICALP.2018.92zbMath1484.68170arXiv1808.10316OpenAlexW2886745396MaRDI QIDQ5002774
Nicole Wein, Shay Solomon, Krzysztof Onak, Baruch Schieber
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1808.10316
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Fully dynamic MIS in uniformly sparse graphs, When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time, Improved Dynamic Graph Coloring
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed \((\varDelta + 1)\)-coloring in the physical model
- Adjacency queries in dynamic sparse graphs
- Leader election in shared spectrum radio networks
- Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
- On the Problem of Decomposing a Graph into n Connected Factors
- Edge-Disjoint Spanning Trees of Finite Graphs
- Bounded Arboricity to Determine the Local Structure of Sparse Graphs
- Short path queries in planar graphs in constant time
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Fully dynamic MIS in uniformly sparse graphs
- Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
- Optimal Dynamic Distributed MIS
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Decomposition of Finite Graphs Into Forests
