Probabilistic analysis of a parallel algorithm for finding maximal independent sets
From MaRDI portal
Publication:3489456
DOI10.1002/rsa.3240010104zbMath0707.68042MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
68W15: Distributed algorithms
Related Items
On the Average Case Complexity of Some P-complete Problems, Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph, On the expected performance of a parallel algorithm for finding maximal independent subsets of a random graph