Tight Analysis of Parallel Randomized Greedy MIS

DOI10.1145/3326165MaRDI QIDQ3384660zbMATH OpenOpenAlexWikidataFDO

Authors 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 algorithmmaximal independent setparallel algorithmsPRAM

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
• Tight bounds for parallel randomized load balancing
• Tight bounds for parallel randomized load balancing, extended abstract
• Analysis of parallel algorithms for finding a maximal independent set in a random hypergraph
• An optimal bit complexity randomized distributed MIS algorithm
• scientific article; zbMATH DE number 1302200
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets

Cited in

(2)

• Derandomized concentration bounds for polynomials, and hypergraph maximal independent set
• Tight analysis of parallel randomized greedy MIS

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 Q3384660)