@inproceedings { ,
title = {The computational complexity of the parallel knock-out problem},
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.},
conference = {7th Latin American Theoretical Informatics Symposium (LATIN 2006)},
doi = {10.1007/11682462\_26},
isbn = {9783540327554},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {250-261},
publicationstatus = {Published},
publisher = {Springer Verlag},
keyword = {Network Engineering, Science and Theory in Durham (NESTiD), Algorithms and Complexity in Durham (ACiD), Parallel knock-out, Graphs, Computational complexity.},
year = {2006},
author = {Broersma, H. and Johnson, M. and Paulusma, D. and Stewart, I.A.}
}