Tight Analysis of Parallel Randomized Greedy MIS

DOI10.1145/3326165zbMATH Open1484.68322OpenAlexW2993198966WikidataQ126666905 ScholiaQ126666905MaRDI QIDQ3384660

Manuela Fischer, Andreas Noever

Publication date: 16 December 2021

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3326165

zbMATH Keywords

greedy algorithmparallel algorithmsPRAMmaximal independent set

Mathematics Subject Classification ID

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

Recommendations

• Unnamed Item 👍 👎
• Unnamed Item 👍 👎
• Tight bounds for parallel randomized load balancing 👍 👎
• An optimal bit complexity randomized distributed MIS algorithm 👍 👎
• Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph 👍 👎
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets 👍 👎
• Tight bounds for parallel randomized load balancing 👍 👎

This page was built for publication: Tight Analysis of Parallel Randomized Greedy MIS