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

Hajo Broersma, Ton Kloks, Dieter Kratsch, Haiko Müller

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

9 Citations (Scopus)

Abstract

A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A, the set A∖{a} is contained in one component of G-N[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.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998, Proceedings
EditorsJuraj Hromkovič, Ondrej Sýkora
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages88-99
Number of pages12
ISBN (Electronic)978-3-540-49494-2
ISBN (Print)978-3-540-65195-6
DOIs
Publication statusPublished - 1998
Event24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1998 - Smolenice Castle, Smolenice, Slovakia
Duration: 18 Jun 199820 Jun 1998
Conference number: 24

Publication series

NameLecture notes in computer science
PublisherSpringer
Number1517
Volume1517
ISSN (Print)0302-9743

Conference

Conference24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1998
Abbreviated titleWG
CountrySlovakia
CitySmolenice
Period18/06/9820/06/98

Fingerprint Dive into the research topics of 'A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking'. Together they form a unique fingerprint.

Cite this