### Abstract

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

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 | Italy |

City | Bologna |

Period | 7/07/97 → 11/07/97 |

### Fingerprint

### Keywords

- IR-92411
- METIS-140801

### Cite this

*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

}

*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, Haitze J.; Kloks, Ton; Kloks, A.J.J.; Kratsch, Dieter; Müller, Haiko.

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

TY - GEN

T1 - Independent sets in asteroidal triple-free graphs

AU - Broersma, Haitze J.

AU - Kloks, Ton

AU - Kloks, A.J.J.

AU - Kratsch, Dieter

AU - Müller, Haiko

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(n 2 · (¯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 2 · (¯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(n 2 · (¯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 2 · (¯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.

KW - IR-92411

KW - METIS-140801

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

ER -