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

PDF
Restricted to UT campus only: Request a copy
626Kb

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
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/67840
Official URL:	http://dx.doi.org/10.1016/j.tcs.2008.03.024
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page