Parallel knock-out schemes in networks

H.J. Broersma, F.V. Fomin, G.J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

We consider parallel knock-out schemes, a procedure on graphs introduced by Lampert and Slater in 1997 in which each vertex eliminates exactly one of its neighbors in each round. We are considering cases in which after a finite number of rounds, where the minimimum number is called the parallel knock-out number, no vertices of the graph are left. We derive a number of combinatorial and algorithmical results on parallel knock-out numbers. We observe that for families of sparse graphs (like planar graphs, or graphs with bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices, which is basically tight for trees. Furthermore, we construct a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach, whereas the general problem is known to be NP-hard. Finally we show that claw-free graphs with minimum degree at least 2 have parallel knock-out number at most 2, and that the lower bound on the minimum degree is best possible.
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science (Proceedings 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004)
Place of PublicationBerlin
PublisherSpringer
Pages204-214
DOIs
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
Volume3153
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Parallel knock-out schemes in networks'. Together they form a unique fingerprint.

  • Cite this

    Broersma, H. J., Fomin, F. V., & Woeginger, G. J. (2004). Parallel knock-out schemes in networks. In Mathematical Foundations of Computer Science (Proceedings 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004) (pp. 204-214). (Lecture Notes in Computer Science; Vol. 3153). Springer. https://doi.org/10.1007/978-3-540-28629-5_13