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).
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 <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) |
Status: | Peer-reviewed |
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 |
Date accepted: | No date available |
Date deposited: | 11 December 2015 |
Date of first online publication: | February 2006 |
Date first made open access: | No date available |
Save or Share this output
Export: | |
Look up in GoogleScholar |