On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph

DOI10.1002/rsa.3240030210zbMath0764.68062OpenAlexW2006057641WikidataQ57401593 ScholiaQ57401593MaRDI QIDQ3990223

Neil J. Calkin, Luděk Kučera, Alan M. Frieze

Publication date: 28 June 1992

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240030210

zbMATH Keywords

greedy algorithmlexicographically first maximal independent set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cites Work

• Probabilistic analysis of a parallel algorithm for finding maximal independent sets
• A taxonomy of problems with fast parallel algorithms
• Probability Inequalities for Sums of Bounded Random Variables

This page was built for publication: On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph