A fast and simple randomized parallel algorithm for the maximal independent set problem

DOI10.1016/0196-6774(86)90019-2zbMath0631.68063OpenAlexW1964089073WikidataQ29396733 ScholiaQ29396733MaRDI QIDQ3768419

Alon Itai, László Babai, Noga Alon

Publication date: 1986

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(86)90019-2

zbMATH Keywords

expected running timeparallel randomized algorithmconcurrent-read concurrent-write PRAMexclusive- read exclusive-write PRAMmaximal independent set in a graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items

Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms, MODp-tests, almost independence and small probability spaces, Unnamed Item, Neighborhood graphs and distributed Δ+1-coloring, Low-diameter graph decomposition is in NC, A parallel algorithmic version of the local lemma, Randomized OBDD-Based Graph Algorithms, Polynomial Data Structure Lower Bounds in the Group Model, Threshold Functions for H-factors, Local-Global Phenomena in Graphs, Network Decomposition and Distributed Derandomization (Invited Paper), Unnamed Item, Deterministic Massively Parallel Connectivity, Node and edge averaged complexities of local graph problems, Time-optimal construction of overlay networks, Exact distributed sampling, Paradigms for Unconditional Pseudorandom Generators, A note on the network coloring game: a randomized distributed \((\Delta+1)\)-coloring algorithm, Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering, Unnamed Item, 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, ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS, Simple Neural-Like P Systems for Maximal Independent Set Selection, Round Compression for Parallel Matching Algorithms, Distributed Graph Algorithms and their Complexity: An Introduction, Hierarchy Theorems for Property Testing, Fully dynamic MIS in uniformly sparse graphs, Bounded Independence Plus Noise Fools Products, Unnamed Item, Unnamed Item, Unnamed Item, How long it takes for an ordinary node with an ordinary ID to output?, On the Microscopic View of Time and Messages, Simple and local independent set approximation, Improved distributed algorithms for coloring interval graphs with application to multicoloring trees, Polynomial hash functions are reliable, Algorithms – ESA 2004, Distributed algorithms for the Lovász local lemma and graph coloring, Equilibria of Games in Networks for Local Tasks, Distributed Approximate Maximum Matching in the CONGEST Model., Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs, When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time, Distributed Reconfiguration of Maximal Independent Sets, Balanced Hashing, Color Coding and Approximate Counting, Moments Tensors, Hilbert's Identity, and k-wise Uncorrelated Random Variables, On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$, Unnamed Item, Monotone circuit lower bounds from robust sunflowers, Unnamed Item, Distributed Lower Bounds for Ruling Sets, Introduction to local certification, Nearly-perfect hypergraph packing is in NC, Randomized OBDD-based graph algorithms, An approximation algorithm for the maximum traveling salesman problem, 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, The probabilistic method yields deterministic parallel algorithms, Design patterns in beeping algorithms: examples, emulation, and analysis, Distributed computing with advice: information sensitivity of graph coloring, A global parallel algorithm for the hypergraph transversal problem, On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs, Tracing a single user, Point sets with distinct distances, A connection between random variables and latin \(k\)-cubes, On-board vehicle data stream monitoring using mine-fleet and fast resource constrained monitoring of correlation matrices, 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, A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting, Designing checkers for programs that run in parallel, Tight approximations for resource constrained scheduling and bin packing, Exact learning of juntas from membership queries, Distributed minimum dominating set approximations in restricted families of graphs, On construction of \(k\)-wise independent random variables, Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM, On the power of two-point based sampling, A fast distributed algorithm for \((\Delta+1)\)-edge-coloring, On deterministic approximation of DNF, Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions, (De)randomized construction of small sample spaces in \(\mathcal{NC}\), Kernel and fast algorithm for dense triplet inconsistency, 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, Distributed minimum vertex coloring and maximum independent set in chordal graphs, Derandomized Construction of Combinatorial Batch Codes, Distributed algorithms for random graphs, 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, Computing large independent sets in a single round, Hierarchy theorems for property testing, Distributed transactional memory for metric-space networks, Beeping a maximal independent set, Toward more localized local algorithms: removing assumptions concerning global knowledge, 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, Fooling views: a new lower bound technique for distributed computations under congestion, Exploiting a hypergraph model for finding Golomb rulers, Approximate inference in Bayesian networks: parameterized complexity results, An optimal bit complexity randomized distributed MIS algorithm, Distributed discovery of large near-cliques, Local randomness in pseudorandom sequences, A randomized NC algorithm for the maximal tree cover problem, The fourth moment in Luby's distribution, Improved distributed \(\Delta\)-coloring, Generalized sum graphs, The maximal \(f\)-dependent set problem for planar graphs is in NC, Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas, Uniform dilations, Approximation algorithm for DNF under distributions with limited independence, Parity check matrices and product representations of squares, Cost-sharing mechanisms for network design, 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, Local computation algorithms for graphs of non-constant degrees, Combinatorial algorithms for distributed graph coloring, Architecting the finite element method pipeline for the GPU, Randomized distributed decision, An optimal maximal independent set algorithm for bounded-independence graphs, Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition, On the complexity of constructing pseudorandom functions (especially when they don't exist), Dynamic networks of finite state machines, Local algorithms for sparse spanning graphs, Linear programming bounds for codes via a covering argument, Quantum Property Testing for Bounded-Degree Graphs, On the Circuit Complexity of Perfect Hashing, A deterministic view of random sampling and its use in geometry, Efficient computation of sparse structures, A fast parallel algorithm for finding Hamiltonian cycles in dense graphs, Combinatorial Algorithms for Distributed Graph Coloring, Reducing complexity assumptions for statistically-hiding commitment, Almost \(k\)-wise independence versus \(k\)-wise independence, Approximating hyper-rectangles: Learning and pseudorandom sets, An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract), Improved parameterized set splitting algorithms: A Probabilistic approach, Improved algorithms via approximations of probability distributions, 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, The space complexity of approximating the frequency moments, Removing randomness in parallel computation without a processor penalty, Distributed coloring algorithms for triangle-free graphs, Low diameter graph decompositions, The maximum clique problem, A processor efficient MIS algorithm on random graphs, Voting paradoxes and digraphs realizations, Graph theoretical issues in computer networks, Probabilistic methods in coloring and decomposition problems, Distributed algorithms for matching in hypergraphs