Constructing a Maximal Independent Set in Parallel

DOI10.1137/0402028zbMath0679.68127OpenAlexW1997802297MaRDI QIDQ4729373

Thomas H. Spencer, Mark K. Goldberg

Publication date: 1989

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/524daf9f17f4083898d4f5019baf8264eafb08d9

zbMATH Keywords

maximal independent setEREW PRAM modeldeterministic NC-algorithm

Mathematics Subject Classification ID

Related Items (20)

Fast parallel constraint satisfaction ⋮ An optimal parallel algorithm for maximal matching ⋮ A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity ⋮ On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs ⋮ Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ The parallel complexity of elimination ordering procedures ⋮ The maximal f-dependent set problem for planar graphs is in NC ⋮ Optimal parallel 3-coloring algorithm for rooted trees and its applications ⋮ Using maximal independent sets to solve problems in parallel ⋮ The maximal \(f\)-dependent set problem for planar graphs is in NC ⋮ An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3 ⋮ An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects ⋮ Approximating matchings in parallel ⋮ Optimal circular arc representations: Properties, recognition, and construction ⋮ A fast parallel algorithm for finding Hamiltonian cycles in dense graphs ⋮ OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS ⋮ AN EFFICIENT NC ALGORITHM FOR APPROXIMATE MAXIMUM WEIGHT MATCHING ⋮ Fast parallel constraint satisfaction ⋮ The maximum clique problem

This page was built for publication: Constructing a Maximal Independent Set in Parallel