A Simple Parallel Algorithm for the Maximal Independent Set Problem
From MaRDI portal
Publication:3756533
DOI10.1137/0215074zbMATH Open0619.68058DBLPjournals/siamcomp/Luby86OpenAlexW2100061495WikidataQ55953005 ScholiaQ55953005MaRDI QIDQ3756533FDOQ3756533
Authors: Michael Luby 
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215074
Recommendations
- A fast 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
- Constructing a Maximal Independent Set in Parallel
- A processor efficient MIS algorithm on random graphs
parallel algorithmmaximal independent setparallel computationsrandomizing algorithmspairwise independences
Cited In (only showing first 100 items - show all)
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A fast parallel algorithm for the maximal independent set problem
- Symmetry breaking depending on the chromatic number or the neighborhood growth
- A fast and efficient NC algorithm for maximal matching
- A framework for automated distributed implementation of component-based models
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Removing randomness in parallel computation without a processor penalty
- The probabilistic method yields deterministic parallel algorithms
- Combinatorial algorithms for distributed graph coloring
- Fast deterministic distributed algorithms for sparse spanners
- The maximum clique problem
- Randomized geometric algorithms and pseudorandom generators
- Improved algorithms via approximations of probability distributions
- Distributed algorithms for random graphs
- Adapting parallel algorithms to the W-stream model, with applications to graph problems
- A bounded-risk mechanism for the kidney exchange game
- A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Highly resilient correctors for polynomials
- Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
- On vertex independence number of uniform hypergraphs
- Title not available (Why is that?)
- Coloring unstructured radio networks
- Threshold Functions for H-factors
- Nearly-perfect hypergraph packing is in NC
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Space-efficient local computation algorithms
- A framework for scalable greedy coloring on distributed-memory parallel computers
- An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
- Low discrepancy sets yield approximate min-wise independent permutation families
- Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains
- Trading bit, message, and time complexity of distributed algorithms
- On possible dependence structures of a set of random variables
- Leveraging Linial’s Locality Limit
- Matching theory -- a sampler: From Dénes König to the present
- Local-Global Phenomena in Graphs
- New techniques and tighter bounds for local computation algorithms
- Variations on algebraic recursive multilevel solvers (ARMS) for the solution of CFD problems
- Revisiting iterated attacks in the context of decorrelation theory
- Polynomial hash functions are reliable (extended abstract)
- Bounds on contention management algorithms
- Graph coloring on coarse grained multicomputers
- Low diameter graph decompositions
- A probing method for computing the diagonal of a matrix inverse.
- Approximating hyper-rectangles: Learning and pseudorandom sets
- Distributed computing with advice: information sensitivity of graph coloring
- An optimal parallel algorithm for maximal matching
- A fine-grained analysis of a simple independent set algorithm
- On the complexity of distributed graph coloring with local minimality constraints
- Approximation in (Poly-) Logarithmic Space
- A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
- Almost \(k\)-wise independence versus \(k\)-wise independence
- Visual cryptography on graphs
- Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
- Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
- Application of multilevel scheme and two level discretization for POD based model order reduction of nonlinear transient heat transfer problems
- Efficient computation of sparse structures
- An optimal bit complexity randomized distributed MIS algorithm
- Fast primal-dual distributed algorithms for scheduling and matching problems
- An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
- Distributed minimum dominating set approximations in restricted families of graphs
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
- \textit{BoomerAMG}: A parallel algebraic multigrid solver and preconditioner
- Combinatorial techniques for universal hashing
- Window-based greedy contention management for transactional memory: theory and practice
- Distributed approximation of capacitated dominating sets
- Cost-sharing mechanisms for network design
- An introduction to randomized algorithms
- Distributed coloring algorithms for triangle-free graphs
- A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph
- Distributed discovery of large near-cliques
- Computational complexity of the perfect matching problem in hypergraphs with subcritical density
- AmgX: a library for GPU accelerated algebraic multigrid and preconditioned iterative methods
- Deterministic parallel algorithms for bilinear objective functions
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- Approximation in (poly-) logarithmic space
- Local computation algorithms for graphs of non-constant degrees
- PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES
- (Probabilistic) recurrence relations revisited
- (De)randomized construction of small sample spaces in \(\mathcal{NC}\)
- A simple proof that finding a maximal independent set in a graph is in NC
- An optimal maximal independent set algorithm for bounded-independence graphs
- The maximal f-dependent set problem for planar graphs is in NC
- Probabilistic recurrence relations revisited
- Universal Hashing via Integer Arithmetic Without Primes, Revisited
- Parallel multigrid solvers for 3D unstructured finite element problems in large deformation elasticity and plasticity
- The complexity of parallel search
- Thread-parallel mesh improvement using face and edge swapping and vertex insertion
- A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
- A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
- Low-diameter graph decomposition is in NC
- Designing checkers for programs that run in parallel
- An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
- Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains
- A 2-approximation NC algorithm for connected vertex cover and tree cover
- Vertex coloring of a graph for memory constrained scenarios
- Algebraic multigrid methods
- Parallel algorithms for routing in nonblocking networks
- Restricted additive Schwarz methods for Markov chains.
This page was built for publication: A Simple 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 Q3756533)
