Tight analysis of parallel randomized greedy MIS

MaRDI QIDQ4608034zbMATH OpenFDO

Authors Manuela Fischer, Andreas Noever

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1707.05124, http://dl.acm.org/citation.cfm?id=3175445

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)

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

Cited in

(7)

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