Skip to main content

Research Repository

Advanced Search

Upper bounds and algorithms for parallel knock-out numbers

Broersma, H.J.; Johnson, M.; Paulusma, D.

Upper bounds and algorithms for parallel knock-out numbers Thumbnail


Authors

H.J. Broersma



Abstract

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph G, the minimum number of required rounds is View the MathML source; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is View the MathML source, where α is the independence number of G. This upper bound is tight. We also show that for reducible K1,p-free graphs at most p−1 rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.

Citation

Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024

Journal Article Type Article
Publication Date Mar 1, 2009
Deposit Date Apr 17, 2009
Publicly Available Date Dec 11, 2015
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 410
Issue 14
Pages 1319-1327
DOI https://doi.org/10.1016/j.tcs.2008.03.024
Keywords Parallel knock-out schemes; Claw-free graphs; Computational complexity.

Files





You might also like



Downloadable Citations