An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
From MaRDI portal
Publication:3136616
DOI10.1137/0406036zbMATH Open0776.68049OpenAlexW2083187124MaRDI QIDQ3136616FDOQ3136616
Thomas H. Spencer, Mark K. Goldberg
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
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
Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Cited In (5)
- 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
- Finding Large Independent Sets in Graphs and Hypergraphs
- Time efficient \(k\)-shot broadcasting in known topology radio networks
- Using maximal independent sets to solve problems in parallel
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)
