### Abstract

Original language | Undefined |
---|---|

Title of host publication | Proceedings of the 7th Latin American Symposium (LATIN 2006) |

Editors | J.R. Correa, A. Hevia, M. Kiwi |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 250-261 |

Number of pages | 12 |

DOIs | |

Publication status | Published - 2006 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Number | 11 |

Volume | 3887 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Keywords

- EWI-8091
- IR-63665
- METIS-238711

### Cite this

*Proceedings of the 7th Latin American Symposium (LATIN 2006)*(pp. 250-261). [10.1007/11682462_26] (Lecture Notes in Computer Science; Vol. 3887, No. 11). Berlin: Springer. https://doi.org/10.1007/11682462_26

}

*Proceedings of the 7th Latin American Symposium (LATIN 2006).*, 10.1007/11682462_26, Lecture Notes in Computer Science, no. 11, vol. 3887, Springer, Berlin, pp. 250-261. https://doi.org/10.1007/11682462_26

**The Computational Complexity of the Parallel Knock-Out Problem.** / Broersma, Haitze J.; Johnson, M.; Paulusma, Daniël; Stewart, I.A.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - The Computational Complexity of the Parallel Knock-Out Problem

AU - Broersma, Haitze J.

AU - Johnson, M.

AU - Paulusma, Daniël

AU - Stewart, I.A.

N1 - 10.1007/11682462_26

PY - 2006

Y1 - 2006

N2 - 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 \ge 2$, 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.

AB - 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 \ge 2$, 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.

KW - EWI-8091

KW - IR-63665

KW - METIS-238711

U2 - 10.1007/11682462_26

DO - 10.1007/11682462_26

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 250

EP - 261

BT - Proceedings of the 7th Latin American Symposium (LATIN 2006)

A2 - Correa, J.R.

A2 - Hevia, A.

A2 - Kiwi, M.

PB - Springer

CY - Berlin

ER -