A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
A subset A of the vertices of a graph G is an asteroidal set if for each vertex a E A a connected component of G-N[a] exists containing A\{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 fur 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.
graph algorithm asteroidal triple treewidth minimum fill-in vertex ranking complexity