Approximating the treewidth of AT-free graphs.

DOI10.1016/S0166-218X(02)00414-6MaRDI QIDQ1408810zbMATH OpenFDO

Authors Ioan Todinca, Vincent Bouchitté

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

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

Recommendations

• scientific article; zbMATH DE number 1696522
• Approximability of the path-distance-width for AT-free graphs
• On treewidth approximations.
• scientific article; zbMATH DE number 1262790
• Approximating the path-distance-width for AT-free graphs and graphs in related classes
• On treewidth approximations
• A managed Bayesian risk approach for decision making alternatives
• Approximation algorithms for treewidth
• Approximating Pathwidth for Graphs of Small Treewidth
• scientific article; zbMATH DE number 772777

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1262790 (Why is no real title available?)
• scientific article; zbMATH DE number 1305094 (Why is no real title available?)
• scientific article; zbMATH DE number 1500539 (Why is no real title available?)
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Complexity of Finding Embeddings in a k-Tree
• Graph minors. II. Algorithmic aspects of tree-width
• Network Flow and Testing Graph Connectivity
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Treewidth and Pathwidth of Permutation Graphs
• Treewidth and minimum fill-in: Grouping the minimal separators

Cited in

(2)

• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• scientific article; zbMATH DE number 1696522 (Why is no real title available?)

This page was built for publication: Approximating the treewidth of AT-free graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1408810)