Approximating the treewidth of AT-free graphs.

DOI10.1016/S0166-218X(02)00414-6zbMath1073.68060MaRDI QIDQ1408810

Ioan Todinca, Vincent Bouchitte

Publication date: 25 September 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

AT-free graphsGraph algorithmsTreewidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizations and algorithmic applications of chordal graph embeddings
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Network Flow and Testing Graph Connectivity
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Treewidth and Pathwidth of Permutation Graphs