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)

Full work available at URL https://doi.org/10.1016/S0166-218X(02)00414-6

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

• Approximating the treewidth of AT-free graphs
• Approximability of the path-distance-width for AT-free graphs
• On treewidth approximations.
• A generalization of AT-free graphs and a generic algorithm for solving treewidth, minimum fill-in and vertex ranking
• 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

• A generalization of AT-free graphs and a generic algorithm for solving treewidth, minimum fill-in and vertex ranking
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Characterizations and algorithmic applications of chordal graph embeddings
• Complexity of Finding Embeddings in a k-Tree
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Listing all potential maximal cliques of a graph
• Minimal triangulations for graphs with ``few minimal separators
• Network Flow and Testing Graph Connectivity
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Treewidth and minimum fill-in: Grouping the minimal separators
• Treewidth and Pathwidth of Permutation Graphs

Cited in

(2)

• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Approximating the treewidth of AT-free graphs

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)