An Improvement of Reed’s Treewidth Approximation

DOI10.7155/jgaa.00593zbMath1498.05255OpenAlexW3092196786MaRDI QIDQ5049997

Mahdi Belbasi, Martin Fuerer

Publication date: 14 November 2022

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00593

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Graph minors. III. Planar tree-width
• Approximation algorithms for treewidth
• S-functions for graphs
• Treewidth. Computations and approximations
• Graph minors. XIII: The disjoint paths problem
• An improvement of Reed's treewidth approximation
• Parametrized complexity theory.
• On non-serial dynamic programming
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Large Induced Subgraphs via Triangulations and CMSO
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Complexity of Finding Embeddings in a k-Tree
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• SOFSEM 2005: Theory and Practice of Computer Science
• Unnamed Item