A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-in and Vertex Ranking

摘要

A subset A of the vertices of a graph G is an asteroidal set if for each vertex α ∈ A, the set A{α} is contained in one component of G - N[α]. 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.