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)

Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel
Equilibria of Games in Networks for Local Tasks
Approximation in (poly-) logarithmic space
Symmetry breaking depending on the chromatic number or the neighborhood growth
(De)randomized construction of small sample spaces in \(\mathcal{NC}\)
PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES
A fast and efficient NC algorithm for maximal matching
A simple proof that finding a maximal independent set in a graph is in NC
Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks
Set cover problems with small neighborhood covers
A fast and simple randomized parallel algorithm for the maximal independent set problem
A fast parallel algorithm for the maximal independent set problem
Component stability in low-space massively parallel computation
(Probabilistic) recurrence relations revisited
Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
A framework for automated distributed implementation of component-based models
Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication
An optimal maximal independent set algorithm for bounded-independence graphs
Introduction to local certification
Removing randomness in parallel computation without a processor penalty
On the probe complexity of local computation algorithms
Probabilistic recurrence relations revisited
The probabilistic method yields deterministic parallel algorithms
An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
Fast deterministic distributed algorithms for sparse spanners
On supervalid inequalities for binary interdiction games
Combinatorial algorithms for distributed graph coloring
The maximal f-dependent set problem for planar graphs is in NC
The maximum clique problem
Parallel approximation of optimization problems
Randomized parallel algorithms
Distributed approximation of k-service assignment
Adapting parallel algorithms to the W-stream model, with applications to graph problems
Distributed algorithms for random graphs
Improved algorithms via approximations of probability distributions
Randomized geometric algorithms and pseudorandom generators
Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
Fooling views: a new lower bound technique for distributed computations under congestion
Communication complexity of approximate maximum matching in the message-passing model
Brief announcement: Self-stabilizing MIS computation in the beeping model
A bounded-risk mechanism for the kidney exchange game
Universal Hashing via Integer Arithmetic Without Primes, Revisited
An Updated Experimental Evaluation of Graph Bipartization Methods
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
Parallel multigrid solvers for 3D unstructured finite element problems in large deformation elasticity and plasticity
scientific article; zbMATH DE number 1418263 (Why is no real title available?)
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
Highly resilient correctors for polynomials
A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
Derandomizing local distributed algorithms under bandwidth restrictions
Algebraic interface-based coarsening AMG preconditioner for multi-scale sparse matrices with applications to radiation hydrodynamics computation.
Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
Combinatorial algorithms for distributed graph coloring
Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC
On vertex independence number of uniform hypergraphs
Nearly-perfect hypergraph packing is in NC
scientific article; zbMATH DE number 1863545 (Why is no real title available?)
Designing checkers for programs that run in parallel
An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
Coloring unstructured radio networks
Threshold Functions for H-factors
Low-diameter graph decomposition is in NC
NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
Self-stabilizing ( +1)-coloring in sublinear (in ) rounds via locally-iterative algorithms
Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains
A framework for scalable greedy coloring on distributed-memory parallel computers
Low discrepancy sets yield approximate min-wise independent permutation families
Space-efficient local computation algorithms
On long-range interpolation operators for aggressive coarsening
An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
Design patterns in beeping algorithms: examples, emulation, and analysis
Loosely-Stabilizing Maximal Independent Set Algorithms with Unreliable Communications
New models and algorithms for RNA pseudoknot order assignment
A parallel algorithm for computing the critical independence number and related sets
IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH
Structuring unreliable radio networks
Distributed algorithms for the Lovász local lemma and graph coloring
Fully dynamic MIS in uniformly sparse graphs
Small-space spectral sparsification via bounded-independence sampling
A new class of AMG interpolation methods based on matrix-matrix multiplications
Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains
A 2-approximation NC algorithm for connected vertex cover and tree cover
Trading bit, message, and time complexity of distributed algorithms
\(H\)-wise independence
On possible dependence structures of a set of random variables
A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH
Vertex coloring of a graph for memory constrained scenarios
Reducing complexity of algebraic multigrid by aggregation.
Matching theory -- a sampler: From Dénes König to the present
Leveraging Linial’s Locality Limit
Resource efficient stabilization for local tasks despite unknown capacity links
An analysis framework for distributed hierarchical directories
Algebraic multigrid methods
Parallel algorithms for routing in nonblocking networks

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)