A simple proof that finding a maximal independent set in a graph is in NC

DOI10.1016/j.ipl.2004.08.007zbMath1173.68851OpenAlexW1990497205MaRDI QIDQ834937

Aaron Windsor

Publication date: 27 August 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.08.007

zbMATH Keywords

parallel algorithmsgraph algorithmsmaximal independent set

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Related Items (1)

Network Decomposition and Distributed Derandomization (Invited Paper)

Cites Work

• A Small Approximately Min-Wise Independent Family of Hash Functions
• An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
• 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 New Parallel Algorithm for the Maximal Independent Set Problem

This page was built for publication: A simple proof that finding a maximal independent set in a graph is in NC