Upper bounds and algorithms for parallel knock-out numbers


Broersma, Hajo and Johnson, Matthew and Paulusma, Daniël and Stewart, Iain A. (2009) Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410 (14). pp. 1319-1327. ISSN 0304-3975

[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 resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{n})$; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is $O(\sqrt{\alpha})$, where $\alpha$ is the independence number of $G$. This upper bound is tight. 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. We also pinpoint a relationship with (locally bijective) graph homomorphisms.

Item Type:Article
Copyright:© 2009 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/67840
Official URL:https://doi.org/10.1016/j.tcs.2008.03.024
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page