A simple proof that finding a maximal independent set in a graph is in NC
From MaRDI portal
(Redirected from Publication:834937)
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 New Parallel Algorithm for the Maximal Independent Set Problem
- 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
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)
