Independent sets in asteroidal triple-free graphs

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

8 Citations (Scopus)
162 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming
Subtitle of host publication24th International Colloquium, ICALP '97 Bologna, Italy, July 7–11, 1997, Proceedings
EditorsPierpaolo Degano, Roberto Gorrieri, Alberto Marchetti-Spaccamela
Number of pages11
ISBN (Electronic)978-3-540-69194-5
ISBN (Print)978-3-540-63165-1
Publication statusPublished - 1997
Event24th International Colloquium on Automata, Languages and Programming, ICALP 1997 - Bologna, Italy
Duration: 7 Jul 199711 Jul 1997
Conference number: 24

Publication series

NameLecture notes in computer science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Colloquium on Automata, Languages and Programming, ICALP 1997
Abbreviated titleICALP


Dive into the research topics of 'Independent sets in asteroidal triple-free graphs'. Together they form a unique fingerprint.

Cite this