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 (only showing first 100 items - show all)

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

This page was built for publication: A fast and simple randomized parallel algorithm for the maximal independent set problem