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)

Parallel derandomization for coloring
Local-Global Phenomena in Graphs
Revisiting iterated attacks in the context of decorrelation theory
New techniques and tighter bounds for local computation algorithms
Variations on algebraic recursive multilevel solvers (ARMS) for the solution of CFD problems
Best of two local models: centralized local and distributed local algorithms
Sub-logarithmic distributed algorithms for metric facility location
Restricted additive Schwarz methods for Markov chains.
Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
Bounds on contention management algorithms
Approximating bipartite minimum vertex cover in the Congest model
Synthesizing optimal bias in randomized self-stabilization
Graph coloring on coarse grained multicomputers
Low diameter graph decompositions
Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
Polynomial hash functions are reliable (extended abstract)
Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
Distributed MIS in O( n) awake complexity
Distributed (+1)-coloring via ultrafast graph shattering
Distributed transactional memory for general networks
A processor efficient MIS algorithm on random graphs
Graph theoretical issues in computer networks
Simple and local independent set approximation
Approximating hyper-rectangles: Learning and pseudorandom sets
Spectral sparsification via bounded-independence sampling
Graph coloring via degeneracy in streaming and other space-conscious models
An optimal parallel algorithm for maximal matching
Distributed computing with advice: information sensitivity of graph coloring
A probing method for computing the diagonal of a matrix inverse.
Encryption modes with almost free message integrity
An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects
Design and implementation of a parallel Markowitz threshold algorithm
A family of constrained pressure residual preconditioners for parallel reservoir simulations.
A fine-grained analysis of a simple independent set algorithm
scientific article; zbMATH DE number 7650083 (Why is no real title available?)
Self-stabilizing MIS computation in the beeping model
Distributed transactional memory for metric-space networks
Probabilistic analysis of a parallel algorithm for finding maximal independent sets
A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
Almost \(k\)-wise independence versus \(k\)-wise independence
Properties of the graph modularity matrix and its applications
Visual cryptography on graphs
On the complexity of distributed graph coloring with local minimality constraints
An adaptive multigrid method based on path cover
Approximation in (Poly-) Logarithmic Space
Local randomness in pseudorandom sequences
Local distributed rounding: generalized to MIS, matching, set cover, and beyond
Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds
(1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
Distributed MIS in O(log log n) Awake Complexity
Distributed MIS with Low Energy and Time Complexities
Distributed Symmetry Breaking on Power Graphs via Sparsification
Distributed Self-Stabilizing MIS with Few States and Weak Communication
Optimal Message-Passing with Noisy Beeps
Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization
Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings
A New Parallel Algorithm for the Maximal Independent Set Problem
Application of multilevel scheme and two level discretization for POD based model order reduction of nonlinear transient heat transfer problems
A note on the network coloring game: a randomized distributed (+1)-coloring algorithm
Distributed minimum vertex coloring and maximum independent set in chordal graphs
Near-optimal clustering in the \(k\)-machine model
Randomized OBDD-based graph algorithms
Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
Randomized OBDD-based graph algorithms
An optimal bit complexity randomized distributed MIS algorithm
Efficient computation of sparse structures
Graph coloring using GPUs
Fast algorithms for Vizing's theorem on bounded degree graphs
Distributed algorithms for matching in hypergraphs
A highly parallel multilevel Newton-Krylov-Schwarz method with subspace-based coarsening and partition-based balancing for the multigroup neutron transport equation on three-dimensional unstructured meshes
Sublinear graph approximation algorithms
A P-complete graph partition problem
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
Linear-in- lower bounds in the LOCAL model
Distributed Lower Bounds for Ruling Sets
Distributed reconfiguration of maximal independent sets
Faster deterministic distributed MIS and approximate matching
Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
o(log⁴ n) time parallel maximal matching algorithm using linear number of processors
Neighborhood graphs and distributed Δ+1-coloring
\textit{BoomerAMG}: A parallel algebraic multigrid solver and preconditioner
Combinatorial techniques for universal hashing
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
Algebraic multigrid methods for elastic structures with highly discontinuous coefficients
Window-based greedy contention management for transactional memory: theory and practice
Formula dissection: A parallel algorithm for constraint satisfaction
Constructing a Maximal Independent Set in Parallel
Fast parallel constraint satisfaction
Distributed approximation of capacitated dominating sets
Realistic analysis of some randomized algorithms
scientific article; zbMATH DE number 7561507 (Why is no real title available?)
Mobile agents on chordal graphs: maximum independent set and beyond
An introduction to randomized algorithms
Fast parallel constraint satisfaction
Cost-sharing mechanisms for network design
An Improved Distributed Algorithm for Maximal Independent Set
What can be sampled locally?
Distributed symmetry breaking on power graphs via sparsification

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)