Upper bounds and algorithms for parallel knock-out numbers


Broersma, Hajo and Johnson, Matthew and Paulusma, Daniël (2007) Upper bounds and algorithms for parallel knock-out numbers. In: 14th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2007, 5-8 June 2007, Castiglioncello, Italy (pp. pp. 328-340).

[img] PDF
Restricted to UT campus only
: Request a copy
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.
Item Type:Conference or Workshop Item
Copyright:© 2007 Springer
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62061
Official URL:https://doi.org/10.1007/978-3-540-72951-8_26
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 245868