Parallel knock-out schemes in networks

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)


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.
Originele taal-2Engels
TitelMathematical Foundations of Computer Science (Proceedings 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004)
Plaats van productieBerlin
StatusGepubliceerd - 2004

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Parallel knock-out schemes in networks'. Samen vormen ze een unieke vingerafdruk.

Citeer dit