A fast parallel algorithm for the maximal independent set problem

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35)

Recommendations

A fast and simple randomized parallel algorithm for the maximal independent set problem
Constructing a Maximal Independent Set in Parallel
A Simple Parallel Algorithm for the Maximal Independent Set Problem
A New Parallel Algorithm for the Maximal Independent Set Problem
scientific article; zbMATH DE number 219239

Cited in

(79)

A fast and efficient NC algorithm for maximal matching
A simple proof that finding a maximal independent set in a graph is in NC
A Simple Parallel Algorithm for the Maximal Independent Set Problem
A fast and simple randomized parallel algorithm for the maximal independent set problem
Computing transparently: The independent sets in a graph
Removing randomness in parallel computation without a processor penalty
The probabilistic method yields deterministic parallel algorithms
Lower bounds on parallel algorithms for finding the first maximal independent set
The maximal f-dependent set problem for planar graphs is in NC
The maximum clique problem
Parallel approximation of optimization problems
Randomized parallel algorithms
A fast and efficient parallel algorithm for finding a satisfying truth assignment to a 2-CNF formula
Improved algorithms via approximations of probability distributions
The complexity of parallel search
A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
scientific article; zbMATH DE number 1418263 (Why is no real title available?)
A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
Optimal circular arc representations: Properties, recognition, and construction
A global parallel algorithm for the hypergraph transversal problem
Parallel `go with the winners' algorithms in distributed memory models.
On vertex independence number of uniform hypergraphs
Nearly-perfect hypergraph packing is in NC
An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
Threshold Functions for H-factors
Low-diameter graph decomposition is in NC
scientific article; zbMATH DE number 2018605 (Why is no real title available?)
Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
Fully dynamic maximal independent set with sublinear update time
Low discrepancy sets yield approximate min-wise independent permutation families
An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
A parallel algorithm for computing the critical independence number and related sets
IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH
\(H\)-wise independence
On possible dependence structures of a set of random variables
Independent sets in graphs
The Hsu-Robbins-Erdös theorem for the maximum partial sums of quadruplewise independent random variables
Matching theory -- a sampler: From Dénes König to the present
A random NC algorithm for depth first search
Resource efficient stabilization for local tasks despite unknown capacity links
OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS
Local-Global Phenomena in Graphs
On splitting sets in block designs and finding roots of polynomials
Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
Scalable kernelization for maximum independent sets
A processor efficient MIS algorithm on random graphs
Finding Large Independent Sets in Graphs and Hypergraphs
An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects
On distance-d independent set problems for some graph classes
A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
A Lagrangean decomposition for the maximum independent set problem applied to map labeling
Computational aspects of monotone dualization: a brief survey
A New Parallel Algorithm for the Maximal Independent Set Problem
The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
The complexity of the comparator circuit value problem
Parallel algorithms for fractional and maximal independent sets in planar graphs
A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set.
A parallel algorithm for finding a triconnected component separator with an application
A measure for the lexicographically first maximal independent set problem and its limits
Efficient computation of sparse structures
Distributed Lower Bounds for Ruling Sets
o(log⁴ n) time parallel maximal matching algorithm using linear number of processors
Constructing a Maximal Independent Set in Parallel
Fast parallel constraint satisfaction
Parallel graph algorithms that are efficients on average
Fast parallel constraint satisfaction
Maximum independent number for series-parallel networks
Robust characterizations of k-wise independence over product spaces and related testing results
A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph
scientific article; zbMATH DE number 177547 (Why is no real title available?)
scientific article; zbMATH DE number 219239 (Why is no real title available?)
Deterministic parallel algorithms for bilinear objective functions
Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
A parallel algorithm for the maximal path problem
scientific article; zbMATH DE number 847156 (Why is no real title available?)
The fourth moment in Luby's distribution
Using maximal independent sets to solve problems in parallel
The maximal \(f\)-dependent set problem for planar graphs is in NC

This page was built for publication: A fast parallel algorithm for the maximal independent set problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3771607)