A fast parallel algorithm for the maximal independent set problem

DOI10.1145/4221.4226MaRDI QIDQ3771607zbMATH OpenOpenAlexFDO

Authors A. Wigderson, Richard Karp

Publication date 1985

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/4221.4226

zbMATH Keywords

block designsgraph theoryindependent setsparallel computation

Mathematics Subject Classification ID

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

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

(84)

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

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)