A simple proof that finding a maximal independent set in a graph is in NC
From MaRDI portal
Publication:834937
DOI10.1016/J.IPL.2004.08.007zbMATH Open1173.68851OpenAlexW1990497205MaRDI QIDQ834937FDOQ834937
Authors: 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
Recommendations
- A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
- Maximal k-independent sets in graphs
- On the number of maximal independent sets in a graph
- The complexity of some problems on maximal independent sets in graphs
- The maximal \(f\)-dependent set problem for planar graphs is in NC
- An upper bound for the number of maximal independent sets in a graph
- Constraints on the number of maximal independent sets in graphs
- Maximizing the number of independent sets of fixed size in connected graphs with given independence number
- On the maximum independent set problem in graphs of bounded maximum degree
- Maximal independent sets in clique-free graphs
Cites Work
- 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 small approximately min-wise independent family of hash functions
- An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
- A New Parallel Algorithm for the Maximal Independent Set Problem
Cited In (2)
This page was built for publication: A simple proof that finding a maximal independent set in a graph is in NC
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q834937)
