Probabilistic analysis of a parallel algorithm for finding maximal independent sets
From MaRDI portal
Publication:3489456
DOI10.1002/rsa.3240010104zbMath0707.68042OpenAlexW1968067819MaRDI QIDQ3489456
Neil J. Calkin, Alan M. Frieze
Publication date: 1990
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240010104
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Related Items (3)
On the Average Case Complexity of Some P-complete Problems ⋮ On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph ⋮ Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph
This page was built for publication: Probabilistic analysis of a parallel algorithm for finding maximal independent sets
