When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time

DOI10.4230/LIPIcs.ICALP.2019.17OpenAlexW2975721026MaRDI QIDQ5091165

Sepehr Assadi, Shay Solomon

Publication date: 21 July 2022

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

zbMATH Keywords

maximal matchingmaximal independent setsublinear-time algorithmsbounded neighborhood independence

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

Distributed backup placement

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Streaming algorithms for independent sets in sparse hypergraphs
• Local computation algorithms for graphs of non-constant degrees
• On a division property of consecutive integers
• A fast and simple randomized parallel algorithm for maximal matching
• Claw-free graphs---a survey
• Approximating the Caro-Wei bound for independent sets in graph streams
• Distributed large independent sets in one round on bounded-independence graphs
• Sum coloring interval and \(k\)-claw free graphs with application to scheduling dependent jobs
• On graph problems in a semi-streaming model
• Perfect matchings in o( n log n ) time in regular bipartite graphs
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• MIS on trees
• Wireless Scheduling with Power Control
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Randomized greedy matching
• Locality in Distributed Graph Algorithms
• Randomized greedy matching. II
• An Improved Distributed Algorithm for Maximal Independent Set
• On the Complexity of Distributed Network Decomposition
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Fully dynamic MIS in uniformly sparse graphs
• Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
• Fully dynamic maximal independent set with sublinear update time
• Sublinear Algorithms for (Δ + 1) Vertex Coloring
• Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
• Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
• Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• What cannot be computed locally!
• Distributed deterministic edge coloring using bounded neighborhood independence

This page was built for publication: When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time