Eliminating graphs by means of parallel knock-out schemes

Haitze J. Broersma, F.V. Fomin, R. Královič, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)
26 Downloads (Pure)

Abstract

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors. We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number $n$ of vertices; this bound is basically tight for trees. Furthermore, there is 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 we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.
Original languageEnglish
Pages (from-to)92-102
Number of pages11
JournalDiscrete applied mathematics
Volume155
Issue number1/2
DOIs
Publication statusPublished - Jan 2007

Keywords

  • MSC-05C75
  • MSC-05C85
  • MSC-05C35
  • MSC-68R10

Fingerprint Dive into the research topics of 'Eliminating graphs by means of parallel knock-out schemes'. Together they form a unique fingerprint.

Cite this