A simple proof that finding a maximal independent set in a graph is in NC
type: Item
instance of: scholarly article
title: A simple proof that finding a maximal independent set in a graph is in NC
zbMATH Open document ID: 1173.68851
author: Aaron Windsor
published in: Information Processing Letters
publication date: 2009-08-27T00:00:00Z
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 5599154
zbMATH Keywords: parallel algorithms
zbMATH Keywords: graph algorithms
zbMATH Keywords: maximal independent set
MaRDI profile type: Publication
full work available at URL: j.ipl.2004.08.007
OpenAlex ID: W1990497205
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: A New Parallel Algorithm for the Maximal Independent Set Problem
cites work: An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
cites work: A small approximately min-wise independent family of hash functions
cites work: A fast parallel algorithm for the maximal independent set problem
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
DOI: 10.1016/J.IPL.2004.08.007
Recommended article: A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
Recommended article: Maximal k-independent sets in graphs
Recommended article: Q5403002
Recommended article: Q5301767
Recommended article: The maximal \(f\)-dependent set problem for planar graphs is in NC
Recommended article: An upper bound for the number of maximal independent sets in a graph
Recommended article: Constraints on the number of maximal independent sets in graphs
Recommended article: Maximizing the number of independent sets of fixed size in connected graphs with given independence number
Recommended article: On the maximum independent set problem in graphs of bounded maximum degree
Recommended article: Maximal independent sets in clique-free graphs
description: scientific article; zbMATH DE number 5599154