A Simple Parallel Algorithm for the Maximal Independent Set Problem
From MaRDI portal
Publication:3756533
DOI10.1137/0215074zbMath0619.68058OpenAlexW2100061495WikidataQ55953005 ScholiaQ55953005MaRDI QIDQ3756533
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
parallel algorithmparallel computationsmaximal independent setrandomizing algorithmspairwise independences
Related Items
Synthesizing optimal bias in randomized self-stabilization, Thread-parallel mesh improvement using face and edge swapping and vertex insertion, Combinatorial techniques for universal hashing, Nearly-perfect hypergraph packing is in NC, Randomized OBDD-based graph algorithms, A simple proof that finding a maximal independent set in a graph is in NC, Low discrepancy sets yield approximate min-wise independent permutation families, Variations on algebraic recursive multilevel solvers (ARMS) for the solution of CFD problems, An optimal parallel algorithm for maximal matching, The probabilistic method yields deterministic parallel algorithms, Design patterns in beeping algorithms: examples, emulation, and analysis, \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, The complexity of parallel search, A fast parallel coloring of planar graphs with five colors, Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds, A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs, Designing checkers for programs that run in parallel, Distributed minimum dominating set approximations in restricted families of graphs, On construction of \(k\)-wise independent random variables, Guaranteed-quality parallel Delaunay refinement for restricted polyhedral domains, 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, (De)randomized construction of small sample spaces in \(\mathcal{NC}\), Distributed approximation of capacitated dominating sets, Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings, Symmetry breaking depending on the chromatic number or the neighborhood growth, Vertex coloring of a graph for memory constrained scenarios, Distributed algorithms for random graphs, Probabilistic recurrence relations revisited, Distributed reconfiguration of maximal independent sets, On vertex independence number of uniform hypergraphs, What can be sampled locally?, Improved deterministic distributed matching via rounding, Derandomizing local distributed algorithms under bandwidth restrictions, Linear-in-\(\varDelta \) lower bounds in the LOCAL model, Adapting parallel algorithms to the W-stream model, with applications to graph problems, Window-based greedy contention management for transactional memory: theory and practice, A framework for automated distributed implementation of component-based models, Visual cryptography on graphs, Computing large independent sets in a single round, Graph coloring on coarse grained multicomputers, A framework for scalable greedy coloring on distributed-memory parallel computers, Distributed transactional memory for metric-space networks, A P-complete graph partition problem, On possible dependence structures of a set of random variables, Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory, Revisiting iterated attacks in the context of decorrelation theory, Communication complexity of approximate maximum matching in the message-passing model, Fooling views: a new lower bound technique for distributed computations under congestion, An optimal bit complexity randomized distributed MIS algorithm, Fast deterministic distributed algorithms for sparse spanners, Formula dissection: A parallel algorithm for constraint satisfaction, Distributed discovery of large near-cliques, Local randomness in pseudorandom sequences, Distributed approximation of \(k\)-service assignment, Application of multilevel scheme and two level discretization for POD based model order reduction of nonlinear transient heat transfer problems, An introduction to randomized algorithms, Deterministic parallel algorithms for bilinear objective functions, Using maximal independent sets to solve problems in parallel, The fourth moment in Luby's distribution, Improved distributed \(\Delta\)-coloring, The maximal \(f\)-dependent set problem for planar graphs is in NC, Parallel approximation for partial set cover, An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3, Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring, Matching theory -- a sampler: From Dénes König to the present, A bounded-risk mechanism for the kidney exchange game, Highly resilient correctors for polynomials, Local computation algorithms for graphs of non-constant degrees, Combinatorial algorithms for distributed graph coloring, Distributed transactional memory for general networks, Randomized distributed decision, Bounds on contention management algorithms, An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects, New models and algorithms for RNA pseudoknot order assignment, Realistic analysis of some randomized algorithms, Best of two local models: centralized local and distributed local algorithms, An optimal maximal independent set algorithm for bounded-independence graphs, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Approximation in (Poly-) logarithmic space, Empire of colonies: Self-stabilizing and self-organizing distributed algorithm, Sub-logarithmic distributed algorithms for metric facility location, Encryption modes with almost free message integrity, A fast parallel algorithm for finding Hamiltonian cycles in dense graphs, Near-optimal clustering in the \(k\)-machine model, Almost \(k\)-wise independence versus \(k\)-wise independence, Approximating hyper-rectangles: Learning and pseudorandom sets, Improved algorithms via approximations of probability distributions, Loosely-stabilizing maximal independent set algorithms with unreliable communications, 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, Distributed algorithms for matching in hypergraphs, Fast parallel constraint satisfaction, Unnamed Item, AmgX: A Library for GPU Accelerated Algebraic Multigrid and Preconditioned Iterative Methods, New techniques and tighter bounds for local computation algorithms, Neighborhood graphs and distributed Δ+1-coloring, Fast primal-dual distributed algorithms for scheduling and matching problems, Coloring unstructured radio networks, Distributed computing with advice: information sensitivity of graph coloring, Low-diameter graph decomposition is in NC, Parallel algorithms for routing in nonblocking networks, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation, Randomized OBDD-Based Graph Algorithms, Unnamed Item, A 2-approximation NC algorithm for connected vertex cover and tree cover, An anonymous self-stabilizing algorithm for 1-maximal independent set in trees, A PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH FIRST SEARCH, An efficient parallel algebraic multigrid method for 3D injection moulding simulation based on finite volume method, Threshold Functions for H-factors, Local-Global Phenomena in Graphs, o(log4 n) time parallel maximal matching algorithm using linear number of processors, A fast distributed algorithm for \((\Delta+1)\)-edge-coloring, (Probabilistic) recurrence relations revisited, Distributed minimum vertex coloring and maximum independent set in chordal graphs, Unnamed Item, Network Decomposition and Distributed Derandomization (Invited Paper), An Updated Experimental Evaluation of Graph Bipartization Methods, Deterministic Massively Parallel Connectivity, Node and edge averaged complexities of local graph problems, Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel, Algebraic multigrid methods, Time-optimal construction of overlay networks, Beyond the worst-case bisection bound: Fast sorting and ranking on meshes, Colouring perfect planar graphs in parallel, Component stability in low-space massively parallel computation, A note on the network coloring game: a randomized distributed \((\Delta+1)\)-coloring algorithm, Universal Hashing via Integer Arithmetic Without Primes, Revisited, Design and Implementation of a Parallel Markowitz Threshold Algorithm, Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, Unnamed Item, Unnamed Item, Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs, The irreducible vectors of a lattice: some theory and applications, Beeping a maximal independent set, Toward more localized local algorithms: removing assumptions concerning global knowledge, Round Compression for Parallel Matching Algorithms, 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, Leveraging Linial’s Locality Limit, Graph Coloring Using GPUs, Restricted additive Schwarz methods for Markov chains, Fully dynamic MIS in uniformly sparse graphs, Unnamed Item, Cost-sharing mechanisms for network design, A New Class of AMG Interpolation Methods Based on Matrix-Matrix Multiplications, Algebraic multigrid methods for elastic structures with highly discontinuous coefficients, Parallel multigrid solvers for 3D unstructured finite element problems in large deformation elasticity and plasticity, A probing method for computing the diagonal of a matrix inverse, A family of constrained pressure residual preconditioners for parallel reservoir simulations, Unnamed Item, Sublinear Graph Approximation Algorithms, Unnamed Item, Unnamed Item, On the complexity of distributed graph coloring with local minimality constraints, How long it takes for an ordinary node with an ordinary ID to output?, Simple and local independent set approximation, Computing fault-containment times of self-stabilizing algorithms using lumped Markov chains, Polynomial hash functions are reliable, COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY, Dynamic networks of finite state machines, Structuring unreliable radio networks, Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set, Distributed algorithms for the Lovász local lemma and graph coloring, Efficient computation of sparse structures, Equilibria of Games in Networks for Local Tasks, Approximation in (Poly-) Logarithmic Space, Distributed Approximate Maximum Matching in the CONGEST Model., On long-range interpolation operators for aggressive coarsening, Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs, Trading Bit, Message, and Time Complexity of Distributed Algorithms, Combinatorial Algorithms for Distributed Graph Coloring, Distributed Reconfiguration of Maximal Independent Sets, Reducing complexity of algebraic multigrid by aggregation, Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication, An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract), Approximation and heuristic algorithms for computing backbones in asymmetric ad-hoc networks, Set cover problems with small neighborhood covers, A Comparison of Classical and Aggregation-Based Algebraic Multigrid Preconditioners for High-Fidelity Simulation of Wind Turbine Incompressible Flows, An Adaptive Multigrid Method Based on Path Cover, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCH, Robust characterizations of k -wise independence over product spaces and related testing results, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES, Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC, Unnamed Item, Distributed Lower Bounds for Ruling Sets, An analysis framework for distributed hierarchical directories, Distributed coloring algorithms for triangle-free graphs, Introduction to local certification, Algebraic interface‐based coarsening AMG preconditioner for multi‐scale sparse matrices with applications to radiation hydrodynamics computation, The maximal f-dependent set problem for planar graphs is in NC, (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, Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization, Optimal Message-Passing with Noisy Beeps, Distributed Self-Stabilizing MIS with Few States and Weak Communication
