Upper bounds and algorithms for parallel knockout numbers
Broersma, Hajo and Johnson, Matthew and Paulusma, Daniël and Stewart, Iain A. (2009) Upper bounds and algorithms for parallel knockout numbers. Theoretical Computer Science, 410 (14). pp. 13191327. ISSN 03043975
PDF
Restricted to UT campus only : Request a copy 641kB 
Abstract:  We study parallel knockout 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 squareroot conjecture, first posed at MFCS 2004, by showing that for a reducible graph , the minimum number of required rounds is ; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is , where is the independence number of . This upper bound is tight. We also show that for reducible free graphs at most rounds are required. It is already known that the problem of whether a given graph is reducible is NPcomplete. For clawfree 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:  
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 
Repository Staff Only: item control page