Broersma, Hajo and Johnson, Matthew and Paulusma, Daniel and Stewart, Iain A. (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. Berlin: Springer, pp. 250-261. Lecture notes in computer science. (3887).
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 <i>k</i> > 1, the problem of whether a given graph admits a scheme in which all vertices are eliminated in at most <i>k</i> rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time.
|Item Type:||Book chapter|
|Keywords:||Parallel knock-out, Graphs, Computational complexity.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (218Kb)
|Publisher Web site:||https://doi.org/10.1007/11682462_26|
|Publisher statement:||The final publication is available at Springer via https://doi.org/10.1007/11682462_26|
|Record Created:||14 Oct 2009 09:05|
|Last Modified:||01 May 2017 16:18|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|