Constructing a Maximal Independent Set in Parallel

DOI10.1137/0402028MaRDI QIDQ4729373zbMATH OpenOpenAlexFDO

Authors Mark K. Goldberg, Thomas H. Spencer

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

deterministic NC-algorithmEREW PRAM modelmaximal independent set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A New Parallel Algorithm for the Maximal Independent Set Problem
• A fast parallel algorithm for the maximal independent set problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
• A Simple Parallel Algorithm for the Maximal Independent Set Problem

Cited in

(36)

• A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
• Lower bounds on parallel algorithms for finding the first maximal independent set
• A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs
• Optimal parallel 3-coloring algorithm for rooted trees and its applications
• An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
• Approximating matchings in parallel
• Optimal circular arc representations: Properties, recognition, and construction
• Fast parallel constraint satisfaction
• The maximum clique problem
• A processor efficient MIS algorithm on random graphs
• An optimal parallel algorithm for maximal matching
• A simple NC-algorithm for a maximal independent set in a hypergraph of poly-log arboricity
• Parallel algorithms for maximal acyclic sets
• Optimal parallel algorithm for Brooks' colouring bounded degree graphs in logarithmic time on EREW PRAM
• An efficient parallel algorithm for geometrically characterising drawings of a class of 3-D objects
• On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
• An efficient NC algorithm for approximate maximum weight matching
• OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS
• An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Fast parallel constraint satisfaction
• scientific article; zbMATH DE number 219239 (Why is no real title available?)
• scientific article; zbMATH DE number 847156 (Why is no real title available?)
• Network Decomposition and Distributed Derandomization (Invited Paper)
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Computing transparently: The independent sets in a graph
• Network decomposition and maximum independent set. II: Application research
• A work-optimal coarse-grained PRAM algorithm for Lexicographically First Maximal Independent Set.
• The parallel complexity of elimination ordering procedures
• The maximal f-dependent set problem for planar graphs is in NC
• Using maximal independent sets to solve problems in parallel
• The maximal \(f\)-dependent set problem for planar graphs is in NC
• Parallel algorithms for fractional and maximal independent sets in planar graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4729373)