A generalization of AT-free graphs and a generic algorithm for solving triangulation problems

H.J. Broersma, T. Kloks, D. Kratsch, H. Müller

    Research output: Book/ReportReportProfessional

    Abstract

    A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A a connected component of G-N[a] exists containing A\backslash{a} . An asteroidal set of cardinality three is called asteriodal triple and graphs without an asteriodal triple are called AT-free . The maximum cardinality of an asteroidal set of G , denoted by \an(G) , is said to be the asteriodal 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 asteriodal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.
    Original languageEnglish
    Place of PublicationPrague
    PublisherCharles University, Faculty of Mathematics and Physics
    Number of pages21
    Publication statusPublished - 1998

      Fingerprint

    Cite this

    Broersma, H. J., Kloks, T., Kratsch, D., & Müller, H. (1998). A generalization of AT-free graphs and a generic algorithm for solving triangulation problems. Prague: Charles University, Faculty of Mathematics and Physics.