### Abstract

Original language | Undefined |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science, 24th International Workshop, WG’98, Smolenice Castle, Slovak Republic, June 18-20, 1998 |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 88-99 |

Number of pages | 12 |

ISBN (Print) | 3-540-65195-0 |

DOIs | |

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 | Slovakia |

City | Smolenice |

Period | 18/06/98 → 20/06/98 |

### Keywords

- METIS-141075
- IR-92414

### Cite this

*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

}

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

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, 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 -