When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
From MaRDI portal
Publication:5091165
Recommendations
- Sublinear algorithms for ( + 1) vertex coloring
- Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
- Lower Bounds for Maximal Matchings and Maximal Independent Sets
- An optimal maximal independent set algorithm for bounded-independence graphs
- The locality of distributed symmetry breaking
Cites work
- A fast and simple randomized parallel algorithm for maximal matching
- 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 near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- An Improved Distributed Algorithm for Maximal Independent Set
- Approximating the Caro-Wei bound for independent sets in graph streams
- Claw-free graphs---a survey
- Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
- Distributed deterministic edge coloring using bounded neighborhood independence
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Distributed large independent sets in one round on bounded-independence graphs
- Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
- Fully dynamic maximal independent set with sublinear update time
- Fully dynamic maximal matching in O( n) update time
- Fully dynamic MIS in uniformly sparse graphs
- scientific article; zbMATH DE number 1303560 (Why is no real title available?)
- scientific article; zbMATH DE number 1033855 (Why is no real title available?)
- Improved massively parallel computation algorithms for MIS, matching, and vertex cover
- Local computation algorithms for graphs of non-constant degrees
- Locality in Distributed Graph Algorithms
- MIS on trees
- On a division property of consecutive integers
- On graph problems in a semi-streaming model
- On the Complexity of Distributed Network Decomposition
- Perfect matchings in O(n n) time in regular bipartite graphs
- Perfect matchings via uniform sampling in regular bipartite graphs
- Randomized greedy matching
- Randomized greedy matching. II
- Space-efficient local computation algorithms
- Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
- Streaming algorithms for independent sets in sparse hypergraphs
- Sublinear algorithms for ( + 1) vertex coloring
- Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
- The structure of claw-free graphs
- What cannot be computed locally!
- Wireless Scheduling with Power Control
Cited in
(5)- Distributed backup placement
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
- Fully dynamic maximal independent set with sublinear update time
- Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
- Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set
This page was built for publication: When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091165)
