Structural Information and Communication Complexity
Structural Information and Communication Complexity
复制标题
结构信息和通信复杂性
DOI：
10.1007/978-3-540-72951-8_26
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Broersma H
中科院分区：
文献类型：
--
作者：
Broersma H
我们研究了图的并行敲除方案。这些计划进行轮，其中每个幸存的顶点同时消除其幸存的邻居之一;一个图是可约的，如果这样的计划可以消除图中的每个顶点。我们证明了对于一个可约图G，所需的最小圈数为，其中α是G的独立数.这个上界是紧的，结果暗示了在MFCS 2004中首次提出的平方根猜想。我们还证明了对于可约K1，需要至多p-1轮的无p图。已知给定图是否可约的问题是NP-完全的。然而，对于无爪图，我们证明了这个问题可以在多项式时间内解决。
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 graphG, the minimum number of required rounds is, whereαis the independence number ofG. 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 reducibleK1,p-free graphs at mostp− 1 rounds are required. It is already known that the problem of whether a given graph is reducible isNP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time.