Broersma, Hajo; Kloks, Ton; Kratsch, Dieter; Müller, Haiko Independent sets in asteroidal triple-free graphs. (English) Zbl 0918.68072 SIAM J. Discrete Math. 12, No. 2, 276-287 (1999). Summary: An asteroidal triple (AT) 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 AT. We show that there is an \(O(n^{4})\) time algorithm to compute the maximum weight of an independent set for AT-free graphs. Furthermore, we obtain \(O(n^{4})\) time algorithms to solve the independent dominating set and the independent perfect dominating set problems 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. Cited in 1 ReviewCited in 32 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) Keywords:graph algorithms; AT-free graphs; independent set; independent dominating set PDFBibTeX XMLCite \textit{H. Broersma} et al., SIAM J. Discrete Math. 12, No. 2, 276--287 (1999; Zbl 0918.68072) Full Text: DOI