Independent sets in asteroidal triple-free graphs

Hajo Broersma; Ton Kloks; Dieter Kratsch; Haiko Müller

doi:10.1007/3-540-63165-8_229

Independent sets in asteroidal triple-free graphs

Hajo Broersma
, Ton Kloks
, Dieter Kratsch
, Haiko Müller

Discrete Mathematics and Mathematical Programming

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

9 Citations (Scopus)

167 Downloads (Pure)

Abstract

An asteroidal triple is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an asteroidal triple. We show that there is an O(n² · (¯m+1)) time algorithm to compute the maximum cardinality of an independent set for AT-free graphs, where n is the number of vertices and ¯m is the number of non edges of the input graph. Furthermore we obtain O(n² · (¯m+1)) time algorithms to solve the INDEPENDENT DOMINATING SET and the INDEPENDENT PERFECT DOMINATING SET problem on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally we observe that the problems CLIQUE and PARTITION INTO CLIQUES remain NP-complete when restricted to AT-free graphs.

Original language	English
Title of host publication	Automata, Languages and Programming
Subtitle of host publication	24th International Colloquium, ICALP '97 Bologna, Italy, July 7–11, 1997, Proceedings
Editors	Pierpaolo Degano, Roberto Gorrieri, Alberto Marchetti-Spaccamela
Publisher	Springer
Pages	760-770
Number of pages	11
ISBN (Electronic)	978-3-540-69194-5
ISBN (Print)	978-3-540-63165-1
DOIs	https://doi.org/10.1007/3-540-63165-8_229
Publication status	Published - 1997
Event	24th International Colloquium on Automata, Languages and Programming, ICALP 1997 - Bologna, Italy Duration: 7 Jul 1997 → 11 Jul 1997 Conference number: 24

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	1256
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Colloquium on Automata, Languages and Programming, ICALP 1997
Abbreviated title	ICALP
Country/Territory	Italy
City	Bologna
Period	7/07/97 → 11/07/97

Access to Document

10.1007/3-540-63165-8_229

Independent sets in asteroidal triple-free graphs
Broersma, H., Kloks, T., Kratsch, D. & Muller, H., 1996, Enschede: University of Twente. 18 p. (Memorandum; no. 1359)
Research output: Book/Report › Report › Professional

Cite this

Broersma, H., Kloks, T., Kratsch, D., & Müller, H. (1997). Independent sets in asteroidal triple-free graphs. In P. Degano, R. Gorrieri, & A. Marchetti-Spaccamela (Eds.), Automata, Languages and Programming: 24th International Colloquium, ICALP '97 Bologna, Italy, July 7–11, 1997, Proceedings (pp. 760-770). (Lecture notes in computer science; Vol. 1256). Springer. https://doi.org/10.1007/3-540-63165-8_229

Broersma, Hajo ; Kloks, Ton ; Kratsch, Dieter et al. / Independent sets in asteroidal triple-free graphs. Automata, Languages and Programming: 24th International Colloquium, ICALP '97 Bologna, Italy, July 7–11, 1997, Proceedings. editor / Pierpaolo Degano ; Roberto Gorrieri ; Alberto Marchetti-Spaccamela. Springer, 1997. pp. 760-770 (Lecture notes in computer science).

@inproceedings{0b0d221c2c34433083a597e6f6fa4768,

title = "Independent sets in asteroidal triple-free graphs",

abstract = "An asteroidal triple is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an asteroidal triple. We show that there is an O(n2 · (¯m+1)) time algorithm to compute the maximum cardinality of an independent set for AT-free graphs, where n is the number of vertices and ¯m is the number of non edges of the input graph. Furthermore we obtain O(n2 · (¯m+1)) time algorithms to solve the INDEPENDENT DOMINATING SET and the INDEPENDENT PERFECT DOMINATING SET problem on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally we observe that the problems CLIQUE and PARTITION INTO CLIQUES remain NP-complete when restricted to AT-free graphs.",

author = "Hajo Broersma and Ton Kloks and Dieter Kratsch and Haiko M{\"u}ller",

year = "1997",

doi = "10.1007/3-540-63165-8\_229",

language = "English",

isbn = "978-3-540-63165-1",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "760--770",

editor = "Pierpaolo Degano and Roberto Gorrieri and Alberto Marchetti-Spaccamela",

booktitle = "Automata, Languages and Programming",

address = "Germany",

note = "24th International Colloquium on Automata, Languages and Programming, ICALP 1997, ICALP ; Conference date: 07-07-1997 Through 11-07-1997",

}

Broersma, H, Kloks, T, Kratsch, D & Müller, H 1997, Independent sets in asteroidal triple-free graphs. in P Degano, R Gorrieri & A Marchetti-Spaccamela (eds), Automata, Languages and Programming: 24th International Colloquium, ICALP '97 Bologna, Italy, July 7–11, 1997, Proceedings. Lecture notes in computer science, vol. 1256, Springer, pp. 760-770, 24th International Colloquium on Automata, Languages and Programming, ICALP 1997, Bologna, Italy, 7/07/97. https://doi.org/10.1007/3-540-63165-8_229

Independent sets in asteroidal triple-free graphs. / Broersma, Hajo; Kloks, Ton; Kratsch, Dieter et al.
Automata, Languages and Programming: 24th International Colloquium, ICALP '97 Bologna, Italy, July 7–11, 1997, Proceedings. ed. / Pierpaolo Degano; Roberto Gorrieri; Alberto Marchetti-Spaccamela. Springer, 1997. p. 760-770 (Lecture notes in computer science; Vol. 1256).

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

TY - GEN

T1 - Independent sets in asteroidal triple-free graphs

AU - Broersma, Hajo

AU - Kloks, Ton

AU - Kratsch, Dieter

AU - Müller, Haiko

N1 - Conference code: 24

PY - 1997

Y1 - 1997

N2 - An asteroidal triple is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an asteroidal triple. We show that there is an O(n2 · (¯m+1)) time algorithm to compute the maximum cardinality of an independent set for AT-free graphs, where n is the number of vertices and ¯m is the number of non edges of the input graph. Furthermore we obtain O(n2 · (¯m+1)) time algorithms to solve the INDEPENDENT DOMINATING SET and the INDEPENDENT PERFECT DOMINATING SET problem on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally we observe that the problems CLIQUE and PARTITION INTO CLIQUES remain NP-complete when restricted to AT-free graphs.

AB - An asteroidal triple is a set of three vertices such that there is a path between any pair of them avoiding the closed neighborhood of the third. A graph is called AT-free if it does not have an asteroidal triple. We show that there is an O(n2 · (¯m+1)) time algorithm to compute the maximum cardinality of an independent set for AT-free graphs, where n is the number of vertices and ¯m is the number of non edges of the input graph. Furthermore we obtain O(n2 · (¯m+1)) time algorithms to solve the INDEPENDENT DOMINATING SET and the INDEPENDENT PERFECT DOMINATING SET problem on AT-free graphs. We also show how to adapt these algorithms such that they solve the corresponding problem for graphs with bounded asteroidal number in polynomial time. Finally we observe that the problems CLIQUE and PARTITION INTO CLIQUES remain NP-complete when restricted to AT-free graphs.

U2 - 10.1007/3-540-63165-8_229

DO - 10.1007/3-540-63165-8_229

M3 - Conference contribution

SN - 978-3-540-63165-1

T3 - Lecture notes in computer science

SP - 760

EP - 770

BT - Automata, Languages and Programming

A2 - Degano, Pierpaolo

A2 - Gorrieri, Roberto

A2 - Marchetti-Spaccamela, Alberto

PB - Springer

T2 - 24th International Colloquium on Automata, Languages and Programming, ICALP 1997

Y2 - 7 July 1997 through 11 July 1997

ER -

Broersma H, Kloks T, Kratsch D, Müller H. Independent sets in asteroidal triple-free graphs. In Degano P, Gorrieri R, Marchetti-Spaccamela A, editors, Automata, Languages and Programming: 24th International Colloquium, ICALP '97 Bologna, Italy, July 7–11, 1997, Proceedings. Springer. 1997. p. 760-770. (Lecture notes in computer science). doi: 10.1007/3-540-63165-8_229

Independent sets in asteroidal triple-free graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Research output

Independent sets in asteroidal triple-free graphs

Cite this