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

Haitze J. Broersma, Ton Kloks, A.J.J. 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 languageUndefined
Title of host publicationGraph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998
Place of PublicationBerlin
PublisherSpringer
Pages88-99
Number of pages12
ISBN (Print)3-540-65195-0
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

Keywords

  • METIS-141075
  • IR-92414

Cite this

Broersma, H. J., Kloks, T., Kloks, A. J. J., Kratsch, D., & Müller, H. (1998). A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking. In Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998 (pp. 88-99). (Lecture notes in computer science; Vol. 1517, No. 1517). Berlin: Springer. https://doi.org/10.1007/10692760_8
Broersma, Haitze J. ; Kloks, Ton ; Kloks, A.J.J. ; Kratsch, Dieter ; Müller, Haiko. / A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking. Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998. Berlin : Springer, 1998. pp. 88-99 (Lecture notes in computer science; 1517).
@inbook{4f5fd48d045f46c3b6f918b8828f2062,
title = "A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking",
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.",
keywords = "METIS-141075, IR-92414",
author = "Broersma, {Haitze J.} and Ton Kloks and A.J.J. Kloks and Dieter Kratsch and Haiko M{\"u}ller",
year = "1998",
doi = "10.1007/10692760_8",
language = "Undefined",
isbn = "3-540-65195-0",
series = "Lecture notes in computer science",
publisher = "Springer",
number = "1517",
pages = "88--99",
booktitle = "Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998",

}

Broersma, HJ, Kloks, T, Kloks, AJJ, Kratsch, D & Müller, H 1998, A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking. in Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998. Lecture notes in computer science, no. 1517, vol. 1517, Springer, Berlin, pp. 88-99, 24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1998, Smolenice, Slovakia, 18/06/98. https://doi.org/10.1007/10692760_8

A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking. / Broersma, Haitze J.; Kloks, Ton; Kloks, A.J.J.; Kratsch, Dieter; Müller, Haiko.

Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998. Berlin : Springer, 1998. p. 88-99 (Lecture notes in computer science; Vol. 1517, No. 1517).

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

TY - CHAP

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

AU - Broersma, Haitze J.

AU - Kloks, Ton

AU - Kloks, A.J.J.

AU - Kratsch, Dieter

AU - Müller, Haiko

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

KW - METIS-141075

KW - IR-92414

U2 - 10.1007/10692760_8

DO - 10.1007/10692760_8

M3 - Chapter

SN - 3-540-65195-0

T3 - Lecture notes in computer science

SP - 88

EP - 99

BT - Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998

PB - Springer

CY - Berlin

ER -

Broersma HJ, Kloks T, Kloks AJJ, Kratsch D, Müller H. A Generalization of AT-free Graphs and a Generic Algorithm for Solving Treewidth, Minimum Fill-In and Vertex Ranking. In Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998. Berlin: Springer. 1998. p. 88-99. (Lecture notes in computer science; 1517). https://doi.org/10.1007/10692760_8