# zbMATH — the first resource for mathematics

A generalization of AT-free graphs and a generic algorithm for solving triangulation problems. (English) Zbl 1009.68099
Summary: A subset $$A$$ of the vertices of a graph $$G$$ is an asteroidal set if for each vertex $$a\in A$$ a connected component of $$G-N[a]$$ exists containing $$A\setminus \{a\}$$. An asteroidal set of cardinality three is called asteroidal triple and graphs without an asteroidal triple are called $$AT$$-free. The maximum cardinality of an asteroidal set of $$G$$, denoted by an $$(G)$$, is said to be the asteroidal number of $$G$$. We present a scheme for designing algorithms for triangulation problems on graphs. As a consequence, we obtain algorithms to compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteroidal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 68W05 Nonnumerical algorithms
##### Keywords:
asteroidal set; asteroidal triple
Full Text: