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

doi:10.1007/10692760_8

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

9 Citations (Scopus)

7 Downloads (Pure)

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 language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998, Proceedings
Editors	Juraj Hromkovič, Ondrej Sýkora
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	88-99
Number of pages	12
ISBN (Electronic)	978-3-540-49494-2
ISBN (Print)	978-3-540-65195-6
DOIs	https://doi.org/10.1007/10692760_8
Publication status	Published - 1998
Event	24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1998 - Smolenice Castle, Smolenice, Slovakia Duration: 18 Jun 1998 → 20 Jun 1998 Conference number: 24

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Number	1517
Volume	1517
ISSN (Print)	0302-9743

Conference

Conference	24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1998
Abbreviated title	WG
Country/Territory	Slovakia
City	Smolenice
Period	18/06/98 → 20/06/98

Access to Document

10.1007/10692760_8

9 Citations
1 Report

A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
Broersma, H., Kloks, T., Kratsch, D. & Müller, H., 1997, Enschede: University of Twente. 18 p. (Memorandum; no. 1385)
Research output: Book/Report › Report › Professional

Cite this

Broersma, H., Kloks, T., 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 J. Hromkovič, & O. Sýkora (Eds.), Graph-Theoretic Concepts in Computer Science: 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998, Proceedings (pp. 88-99). (Lecture notes in computer science; Vol. 1517, No. 1517). Springer. https://doi.org/10.1007/10692760_8

Broersma, Hajo ; Kloks, Ton ; Kratsch, Dieter et al. / 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, Proceedings. editor / Juraj Hromkovič ; Ondrej Sýkora. Berlin, Heidelberg : 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.",

author = "Hajo Broersma and Ton Kloks and Dieter Kratsch and Haiko M{\"u}ller",

year = "1998",

doi = "10.1007/10692760\_8",

language = "English",

isbn = "978-3-540-65195-6",

series = "Lecture notes in computer science",

publisher = "Springer",

number = "1517",

pages = "88--99",

editor = "Juraj Hromkovi{\v c} and Ondrej S{\'y}kora",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

note = "24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1998, WG ; Conference date: 18-06-1998 Through 20-06-1998",

}

Broersma, H, Kloks, T, 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 J Hromkovič & O Sýkora (eds), Graph-Theoretic Concepts in Computer Science: 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998, Proceedings. Lecture notes in computer science, no. 1517, vol. 1517, Springer, Berlin, Heidelberg, 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, Hajo; Kloks, Ton; Kratsch, Dieter et al.
Graph-Theoretic Concepts in Computer Science: 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998, Proceedings. ed. / Juraj Hromkovič; Ondrej Sýkora. Berlin, Heidelberg: Springer, 1998. p. 88-99 (Lecture notes in computer science; Vol. 1517, No. 1517).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

TY - CHAP

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

AU - Broersma, Hajo

AU - Kloks, Ton

AU - Kratsch, Dieter

AU - Müller, Haiko

N1 - Conference code: 24

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.

U2 - 10.1007/10692760_8

DO - 10.1007/10692760_8

M3 - Chapter

SN - 978-3-540-65195-6

T3 - Lecture notes in computer science

SP - 88

EP - 99

BT - Graph-Theoretic Concepts in Computer Science

A2 - Hromkovič, Juraj

A2 - Sýkora, Ondrej

PB - Springer

CY - Berlin, Heidelberg

T2 - 24th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1998

Y2 - 18 June 1998 through 20 June 1998

ER -

Broersma H, Kloks T, 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 Hromkovič J, Sýkora O, editors, Graph-Theoretic Concepts in Computer Science: 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998, Proceedings. Berlin, Heidelberg: Springer. 1998. p. 88-99. (Lecture notes in computer science; 1517). doi: 10.1007/10692760_8

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Research output

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

Cite this