An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size

DOI10.1137/0406036zbMath0776.68049OpenAlexW2083187124MaRDI QIDQ3136616

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

zbMATH Keywords

independent setTurán's theoremNCCRCW PRAM

Mathematics Subject Classification ID

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

Related Items (2)

A simple proof that finding a maximal independent set in a graph is in NC ⋮ Time efficient \(k\)-shot broadcasting in known topology radio networks

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