@inproceedings{f05b738bcd7442979728677d53b83820,

title = "Upper bounds and algorithms for parallel knock-out numbers",

abstract = "We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We show that, for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{\alpha}$, where $\alpha$ is the independence number of $G$. This upper bound is tight and the result implies the square-root conjecture which was first posed in MFCS 2004. We also show that for reducible $K_{1,p}$-free graphs at most $p - 1$ rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time.",

keywords = "EWI-11586, IR-62061, METIS-245868",

author = "Broersma, {Haitze J.} and Matthew Johnson and Dani{\"e}l Paulusma",

note = "10.1007/978-3-540-72951-8_26 ",

year = "2007",

month = jul,

doi = "10.1007/978-3-540-72951-8_26",

language = "Undefined",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "1",

pages = "328--340",

editor = "Giuseppe Prencipe and Shmuel Zaks",

booktitle = "SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity",

}