Constructing a Maximal Independent Set in Parallel
From MaRDI portal
Publication:4729373
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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
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