Name
Abstract | ||
|---|---|---|
. Using the specic structure of the minimal separators of AT-free graphs, we givea polynomial time algorithm that computes a triangulation whose width is no more thantwice the treewidth of the input graph.1 IntroductionThe treewidth of graphs, introduced by Robertson and Seymour [12], has been intensively studiedin the last years, mainly because many NP-hard problems become solvable in polynomial andeven in linear time when restricted to graphs with small treewidth. These algorithms use ... |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S0166-218X(02)00414-6 | Workshop on Graph-Theoretic Concepts in Computer Science |
Keywords | Field | DocType |
specific structure,at-free graph,minimal separator,treewidth,at-free graphs,polynomial time algorithm,graph algorithms,input graph | Discrete mathematics,Combinatorics,Tree-depth,Partial k-tree,Chordal graph,Clique-sum,Tree decomposition,Treewidth,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
131 | 1 | Discrete Applied Mathematics |
ISBN | Citations | PageRank |
3-540-41183-6 | 3 | 0.46 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Bouchitté | 1 | 172 | 12.07 |
| Ioan Todinca | 2 | 328 | 27.33 |