### Abstract

Original language | Undefined |
---|---|

Title of host publication | SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity |

Editors | Giuseppe Prencipe, Shmuel Zaks |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 328-340 |

Number of pages | 13 |

DOIs | |

Publication status | Published - Jul 2007 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Number | 1 |

Volume | 4474 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Keywords

- EWI-11586
- IR-62061
- METIS-245868

### Cite this

*SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity*(pp. 328-340). [10.1007/978-3-540-72951-8_26] (Lecture Notes in Computer Science; Vol. 4474, No. 1). Berlin: Springer. https://doi.org/10.1007/978-3-540-72951-8_26

}

*SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity.*, 10.1007/978-3-540-72951-8_26, Lecture Notes in Computer Science, no. 1, vol. 4474, Springer, Berlin, pp. 328-340. https://doi.org/10.1007/978-3-540-72951-8_26

**Upper bounds and algorithms for parallel knock-out numbers.** / Broersma, Haitze J.; Johnson, Matthew; Paulusma, Daniël.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Upper bounds and algorithms for parallel knock-out numbers

AU - Broersma, Haitze J.

AU - Johnson, Matthew

AU - Paulusma, Daniël

N1 - 10.1007/978-3-540-72951-8_26

PY - 2007/7

Y1 - 2007/7

N2 - 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.

AB - 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.

KW - EWI-11586

KW - IR-62061

KW - METIS-245868

U2 - 10.1007/978-3-540-72951-8_26

DO - 10.1007/978-3-540-72951-8_26

M3 - Conference contribution

T3 - Lecture Notes in Computer Science

SP - 328

EP - 340

BT - SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity

A2 - Prencipe, Giuseppe

A2 - Zaks, Shmuel

PB - Springer

CY - Berlin

ER -