Tight analysis of parallel randomized greedy MIS

zbMATH Open1403.68333arXiv1707.05124MaRDI QIDQ4608034FDOQ4608034

Authors: Manuela Fischer, Andreas Noever 

Publication date: 15 March 2018

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

Recommendations

• Tight Analysis of Parallel Randomized Greedy MIS
• A processor efficient MIS algorithm on random graphs
• An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets
• A fast and simple randomized parallel algorithm for the maximal independent set problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Parallel algorithms in computer science (68W10)

Cited In (7)

• Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
• Distributed independent sets in interval and segment intersection graphs
• Derandomized concentration bounds for polynomials, and hypergraph maximal independent set
• Fully dynamic MIS in uniformly sparse graphs
• Distributed MIS in O(log log n) Awake Complexity
• Tight Analysis of Parallel Randomized Greedy MIS
• Greedy maximal independent sets via local limits

This page was built for publication: Tight analysis of parallel randomized greedy MIS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608034)