Skip to main content

Research Repository

Advanced Search

The computational complexity of the parallel knock-out problem

Broersma, H.; Johnson, M.; Paulusma, D.; Stewart, I.A.

The computational complexity of the parallel knock-out problem Thumbnail


Authors

H. Broersma



Abstract

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for a given graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers k > 1, the problem of whether a given graph admits a scheme in which all vertices are eliminated in at most k rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time.

Citation

Broersma, H., Johnson, M., Paulusma, D., & Stewart, I. (2006). The computational complexity of the parallel knock-out problem. In LATIN 2006 : theoretical informatics: : 7th Latin American symposium, Valdivia, Chile, March 20-24, 2006 : proceedings (250-261). https://doi.org/10.1007/11682462_26

Conference Name 7th Latin American Theoretical Informatics Symposium (LATIN 2006)
Conference Location Valdivia, Chile
Start Date Mar 20, 2006
End Date Mar 24, 2006
Publication Date Feb 18, 2006
Deposit Date Oct 14, 2009
Publicly Available Date Mar 29, 2024
Publisher Springer Verlag
Pages 250-261
Series Title Lecture notes in computer science
Series Number 3887
Book Title LATIN 2006 : theoretical informatics: : 7th Latin American symposium, Valdivia, Chile, March 20-24, 2006 : proceedings.
ISBN 9783540327554
DOI https://doi.org/10.1007/11682462_26
Keywords Parallel knock-out, Graphs, Computational complexity.

Files





You might also like



Downloadable Citations