Upper bounds and algorithms for parallel knock-out numbers

Haitze J. Broersma, Matthew Johnson, Daniël Paulusma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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 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.
Original languageUndefined
Title of host publicationSIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity
EditorsGiuseppe Prencipe, Shmuel Zaks
Place of PublicationBerlin
PublisherSpringer
Pages328-340
Number of pages13
DOIs
Publication statusPublished - Jul 2007

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Number1
Volume4474
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

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

Cite this

Broersma, H. J., Johnson, M., & Paulusma, D. (2007). Upper bounds and algorithms for parallel knock-out numbers. In G. Prencipe, & S. Zaks (Eds.), 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
Broersma, Haitze J. ; Johnson, Matthew ; Paulusma, Daniël. / Upper bounds and algorithms for parallel knock-out numbers. SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity. editor / Giuseppe Prencipe ; Shmuel Zaks. Berlin : Springer, 2007. pp. 328-340 (Lecture Notes in Computer Science; 1).
@inproceedings{f05b738bcd7442979728677d53b83820,
title = "Upper bounds and algorithms for parallel knock-out numbers",
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 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.",
keywords = "EWI-11586, IR-62061, METIS-245868",
author = "Broersma, {Haitze J.} and Matthew Johnson and Dani{\"e}l Paulusma",
note = "10.1007/978-3-540-72951-8_26",
year = "2007",
month = "7",
doi = "10.1007/978-3-540-72951-8_26",
language = "Undefined",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "1",
pages = "328--340",
editor = "Giuseppe Prencipe and Shmuel Zaks",
booktitle = "SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity",

}

Broersma, HJ, Johnson, M & Paulusma, D 2007, Upper bounds and algorithms for parallel knock-out numbers. in G Prencipe & S Zaks (eds), 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.

SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity. ed. / Giuseppe Prencipe; Shmuel Zaks. Berlin : Springer, 2007. p. 328-340 10.1007/978-3-540-72951-8_26 (Lecture Notes in Computer Science; Vol. 4474, No. 1).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 -

Broersma HJ, Johnson M, Paulusma D. Upper bounds and algorithms for parallel knock-out numbers. In Prencipe G, Zaks S, editors, SIROCCO 2007: 14th International Colloquium on Structural Information and Communication Complexity. Berlin: Springer. 2007. p. 328-340. 10.1007/978-3-540-72951-8_26. (Lecture Notes in Computer Science; 1). https://doi.org/10.1007/978-3-540-72951-8_26