A Simple Parallel Algorithm for the Maximal Independent Set Problem
From MaRDI portal
Publication:3756533
DOI10.1137/0215074zbMATH Open0619.68058DBLPjournals/siamcomp/Luby86OpenAlexW2100061495WikidataQ55953005 ScholiaQ55953005MaRDI QIDQ3756533FDOQ3756533
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)
- (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
- Restricted additive Schwarz methods for Markov chains
- Dynamic networks of finite state machines
- Randomized OBDD-Based Graph Algorithms
- 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 family of constrained pressure residual preconditioners for parallel reservoir simulations
- Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs
- A 2-approximation NC algorithm for connected vertex cover and tree cover
- Algebraic multigrid methods
- Parallel algorithms for routing in nonblocking networks
- Time-optimal construction of overlay networks
- Best of two local models: centralized local and distributed local algorithms
- Synthesizing optimal bias in randomized self-stabilization
- Sub-logarithmic distributed algorithms for metric facility location
- A processor efficient MIS algorithm on random graphs
- Graph theoretical issues in computer networks
- Encryption modes with almost free message integrity
- Probabilistic analysis of a parallel algorithm for finding maximal independent sets
- Local randomness in pseudorandom sequences
- A New Parallel Algorithm for the Maximal Independent Set Problem
- Randomized OBDD-based graph algorithms
- Distributed algorithms for matching in hypergraphs
- A P-complete graph partition problem
- o(log4 n) time parallel maximal matching algorithm using linear number of processors
- Neighborhood graphs and distributed Δ+1-coloring
- Constructing a Maximal Independent Set in Parallel
- Algebraic multigrid methods for elastic structures with highly discontinuous coefficients
- Formula dissection: A parallel algorithm for constraint satisfaction
- Realistic analysis of some randomized algorithms
- Fast parallel constraint satisfaction
- Fast parallel constraint satisfaction
- An Improved Distributed Algorithm for Maximal Independent Set
- Node and edge averaged complexities of local graph problems
- Deterministic parallel algorithms for bilinear objective functions
- Title not available (Why is that?)
- Parallel approximation for partial set cover
- On construction of \(k\)-wise independent random variables
- A fast parallel coloring of planar graphs with five colors
- 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
- 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
- Approximation in (Poly-) logarithmic space
- A framework for automated distributed implementation of component-based models
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- 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
- Polynomial hash functions are reliable
- A probing method for computing the diagonal of a matrix inverse
- 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
- COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY
- Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
- On vertex independence number of uniform hypergraphs
- Title not available (Why is that?)
- Randomized distributed decision
- Coloring unstructured radio networks
- Threshold Functions for H-factors
- AmgX: A Library for GPU Accelerated Algebraic Multigrid and Preconditioned Iterative Methods
- Nearly-perfect hypergraph packing is in NC
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- 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
- Beeping a maximal independent set
- Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains
- An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract)
- 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
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)
