×

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
PDF BibTeX XML Cite
Full Text: DOI