A fast parallel algorithm for the maximal independent set problem
From MaRDI portal
Publication:3771607
DOI10.1145/4221.4226zbMath0633.68026OpenAlexW2026143151MaRDI QIDQ3771607
Avi Wigderson, Richard M. 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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A Lagrangean decomposition for the maximum independent set problem applied to map labeling, Fast parallel constraint satisfaction, Nearly-perfect hypergraph packing is in NC, A parallel algorithm for finding a triconnected component separator with an application, A simple proof that finding a maximal independent set in a graph is in NC, Low discrepancy sets yield approximate min-wise independent permutation families, Unnamed Item, The probabilistic method yields deterministic parallel algorithms, Low-diameter graph decomposition is in NC, A global parallel algorithm for the hypergraph transversal problem, A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity, A fast and efficient NC algorithm for maximal matching, On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs, A parallel algorithm for the maximal path problem, Unnamed Item, A random NC algorithm for depth first search, Threshold Functions for H-factors, Local-Global Phenomena in Graphs, o(log4 n) time parallel maximal matching algorithm using linear number of processors, 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, On vertex independence number of uniform hypergraphs, The Hsu-Robbins-Erdös theorem for the maximum partial sums of quadruplewise independent random variables, The maximal f-dependent set problem for planar graphs is in NC, On splitting sets in block designs and finding roots of polynomials, On possible dependence structures of a set of random variables, The complexity of approximating PSPACE-complete problems for hierarchical specifications, Using maximal independent sets to solve problems in parallel, The fourth moment in Luby's distribution, Computational aspects of monotone dualization: a brief survey, The maximal \(f\)-dependent set problem for planar graphs is in NC, Independent sets in graphs, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, 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, An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects, Efficient computation of sparse structures, Optimal circular arc representations: Properties, recognition, and construction, A fast parallel algorithm for finding Hamiltonian cycles in dense graphs, The complexity of the comparator circuit value problem, IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH, Improved algorithms via approximations of probability distributions, A MEASURE FOR THE LEXICOGRAPHICALLY FIRST MAXIMAL INDEPENDENT SET PROBLEM AND ITS LIMITS, Robust characterizations of k -wise independence over product spaces and related testing results, OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS, Distributed Lower Bounds for Ruling Sets, Fast parallel constraint satisfaction, The maximum clique problem, A processor efficient MIS algorithm on random graphs
