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. Heidelberg: Springer Berlin, 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:||PDF - Accepted Version (218Kb)|
|Publisher Web site:||http://dx.doi.org/10.1007/11682462_26|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/11682462_26|
|Record Created:||14 Oct 2009 09:05|
|Last Modified:||11 Dec 2015 11:21|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|