An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size

DOI10.1137/0406036MaRDI QIDQ3136616zbMATHOpenAlexFDO

Authors Mark K. Goldberg, Thomas H. Spencer

Publication date 14 October 1993

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

Full work available at URL https://doi.org/10.1137/0406036

zbMATH Keywords

independent setNCCRCW PRAMTurán's theorem

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast parallel algorithm for the maximal independent set problem
• An efficient parallel algorithm for computing a large independent set in a planar graph
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Lower bounds on parallel algorithms for finding the first maximal independent set
• A parallel algorithm for computing the critical independence number and related sets
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Constructing a Maximal Independent Set in Parallel
• A Parallel Randomized Algorithm for Finding a Maximal Independent Set in a Linear Hypergraph
• Probabilistic analysis of a parallel algorithm for finding maximal independent sets

Cited in

(5)

• Finding Large Independent Sets in Graphs and Hypergraphs
• Using maximal independent sets to solve problems in parallel
• Time efficient \(k\)-shot broadcasting in known topology radio networks
• A simple proof that finding a maximal independent set in a graph is in NC
• A parallel algorithm for computing the critical independence number and related sets

This page was built for publication: An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size

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