A New Parallel Algorithm for the Maximal Independent Set Problem

DOI10.1137/0218029zbMath0678.68060OpenAlexW2110963759MaRDI QIDQ3835033

Mark K. Goldberg, Thomas H. Spencer

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/1990f14b66f9c281b57579cf4ab0c6581d24a9a1

zbMATH Keywords

parallel computationdeterministic algorithmmaximal independent setNCEREW-processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (17)

A simple proof that finding a maximal independent set in a graph is in NC ⋮ Approximating weighted matchings in parallel ⋮ On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs ⋮ o(log⁴ n) time parallel maximal matching algorithm using linear number of processors ⋮ Designing checkers for programs that run in parallel ⋮ Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM ⋮ On parallel complexity of maximum f-matching and the degree sequence problem ⋮ Finding optimal subgraphs by local search ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ The maximal f-dependent set problem for planar graphs is in NC ⋮ Using maximal independent sets to solve problems in parallel ⋮ The fourth moment in Luby's distribution ⋮ The maximal \(f\)-dependent set problem for planar graphs is in NC ⋮ Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees ⋮ A simple parallel algorithm for computing the diameters of all vertices in a tree and its application ⋮ An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3 ⋮ The maximum clique problem

This page was built for publication: A New Parallel Algorithm for the Maximal Independent Set Problem