A processor efficient MIS algorithm on random graphs

DOI10.1016/0020-0190(94)90094-9zbMath0795.68154OpenAlexW2069800464MaRDI QIDQ1318767

V. Pereyra

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

zbMATH Keywords

parallel algorithmrandom graphindependent sets

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A processor efficient MIS algorithm on random graphs