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.

68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms
Full Text: DOI