A Simple Parallel Algorithm for the Maximal Independent Set Problem

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

Cited in

(only showing first 100 items - show all)

Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
Encryption modes with almost free message integrity
A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
Almost \(k\)-wise independence versus \(k\)-wise independence
The complexity of parallel search
A fast parallel coloring of planar graphs with five colors
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
Local randomness in pseudorandom sequences
An introduction to randomized algorithms
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
Highly resilient correctors for polynomials
Approximating hyper-rectangles: Learning and pseudorandom sets
Removing randomness in parallel computation without a processor penalty
Fast parallel constraint satisfaction
Low diameter graph decompositions
The maximum clique problem
A processor efficient MIS algorithm on random graphs
Graph theoretical issues in computer networks
Combinatorial techniques for universal hashing
An optimal parallel algorithm for maximal matching
The probabilistic method yields deterministic parallel algorithms
\textit{BoomerAMG}: A parallel algebraic multigrid solver and preconditioner
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 construction of \(k\)-wise independent random variables
(De)randomized construction of small sample spaces in \(\mathcal{NC}\)
Probabilistic recurrence relations revisited
Graph coloring on coarse grained multicomputers
Improved algorithms via approximations of probability distributions
Thread-parallel mesh improvement using face and edge swapping and vertex insertion
Randomized OBDD-based graph algorithms
Design patterns in beeping algorithms: examples, emulation, and analysis
Linear-in- lower bounds in the LOCAL model
Computing large independent sets in a single round
Distributed approximation of k-service assignment
A bounded-risk mechanism for the kidney exchange game
Best of two local models: centralized local and distributed local algorithms
Variations on algebraic recursive multilevel solvers (ARMS) for the solution of CFD problems
Designing checkers for programs that run in parallel
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
Randomized geometric algorithms and pseudorandom generators
Window-based greedy contention management for transactional memory: theory and practice
A framework for automated distributed implementation of component-based models
Distributed transactional memory for metric-space networks
Improved distributed \(\Delta\)-coloring
New models and algorithms for RNA pseudoknot order assignment
Approximation in (poly-) logarithmic space
Near-optimal clustering in the \(k\)-machine model
Loosely-stabilizing maximal independent set algorithms with unreliable communications
Distributed algorithms for matching in hypergraphs
Synthesizing optimal bias in randomized self-stabilization
Vertex coloring of a graph for memory constrained scenarios
Distributed reconfiguration of maximal independent sets
What can be sampled locally?
Improved deterministic distributed matching via rounding
Derandomizing local distributed algorithms under bandwidth restrictions
Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
Communication complexity of approximate maximum matching in the message-passing model
Fooling views: a new lower bound technique for distributed computations under congestion
Parallel approximation for partial set cover
Combinatorial algorithms for distributed graph coloring
Distributed transactional memory for general networks
An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects
Realistic analysis of some randomized algorithms
Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains
Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks
Set cover problems with small neighborhood covers
An analysis framework for distributed hierarchical directories
Distributed coloring algorithms for triangle-free graphs
Fast primal-dual distributed algorithms for scheduling and matching problems
Coloring unstructured radio networks
Distributed computing with advice: information sensitivity of graph coloring
A 2-approximation NC algorithm for connected vertex cover and tree cover
An anonymous self-stabilizing algorithm for 1-maximal independent set in trees
Toward more localized local algorithms: removing assumptions concerning global knowledge
Cost-sharing mechanisms for network design
Algebraic multigrid methods for elastic structures with highly discontinuous coefficients
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
New techniques and tighter bounds for local computation algorithms
A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
Distributed minimum vertex coloring and maximum independent set in chordal graphs
The irreducible vectors of a lattice: some theory and applications
Efficient computation of sparse structures
Reducing complexity of algebraic multigrid by aggregation.
Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication
Robust characterizations of k-wise independence over product spaces and related testing results
Nearly-perfect hypergraph packing is in NC
A fine-grained analysis of a simple independent set algorithm
Low discrepancy sets yield approximate min-wise independent permutation families
On the complexity of distributed graph coloring with local minimality constraints
Computational complexity of the perfect matching problem in hypergraphs with subcritical density
On long-range interpolation operators for aggressive coarsening
Trading bit, message, and time complexity of distributed algorithms
Combinatorial algorithms for distributed graph coloring
An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
Graph coloring using GPUs
scientific article; zbMATH DE number 4201596 (Why is no real title available?)

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)