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: Contribution to journalArticleAcademicpeer-review

9 Citations (Scopus)

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
Pages (from-to)594-610
Number of pages17
JournalAlgorithmica
Volume32
Issue number4
DOIs
Publication statusPublished - 2002

Keywords

  • Graph
  • Algorithm
  • Complexity
  • Asteroidal triple
  • Treewidth
  • Minimum fill-in
  • Vertex ranking

Fingerprint Dive into the research topics of 'A generalization of AT-free graphs and a generic algorithm for solving triangulation problems'. Together they form a unique fingerprint.

Cite this