A processor efficient MIS algorithm on random graphs
From MaRDI portal
Publication:1318767
DOI10.1016/0020-0190(94)90094-9zbMath0795.68154MaRDI QIDQ1318767
Publication date: 5 April 1994
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)90094-9
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
68R10: Graph theory (including graph drawing) in computer science
68W15: Distributed algorithms
Cites Work
- Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A fast parallel algorithm for the maximal independent set problem
- A review of random graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item