On treewidth approximations.

DOI10.1016/S0166-218X(03)00440-2zbMath1035.05087MaRDI QIDQ1427177

Dieter Kratsch, Ioan Todinca, Haiko Müller, Vincent Bouchitte

Publication date: 14 March 2004

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

zbMATH Keywords

Approximation algorithmTreewidthGraph algorithmAsteroidal numberMinimal separator

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (11)

Space saving by dynamic algebraization based on tree-depth ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Treewidth governs the complexity of target set selection ⋮ Compact navigation and distance oracles for graphs with small treewidth ⋮ Approximation algorithms for digraph width parameters ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Treewidth computations. I: Upper bounds ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tree decompositions and social graphs

Cites Work

• Decomposition by clique separators
• A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
• Characterizations and algorithmic applications of chordal graph embeddings
• Listing all potential maximal cliques of a graph
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Fast Approximate Graph Partitioning Algorithms
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Listing all Minimal Separators of a Graph
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• On the structure of graphs with bounded asteroidal number
• Unnamed Item
• Unnamed Item

This page was built for publication: On treewidth approximations.