An improvement of Reed's treewidth approximation

DOI10.7155/JGAA.00593MaRDI QIDQ5049997zbMATH OpenOpenAlexFDO

Authors Mahdi Belbasi, Martin Fürer

Publication date 14 November 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

Recommendations

• A c^k n 5-approximation algorithm for treewidth
• Approximation algorithms for treewidth
• Approximate tree decompositions of planar graphs in linear time
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• An improved algorithm for finding tree decompositions of small width

Cites work

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

Cited in

(11)

• On treewidth approximations.
• Algorithms for improving the quality of \(R\)-trees
• A c^k n 5-approximation algorithm for treewidth
• scientific article; zbMATH DE number 219228 (Why is no real title available?)
• scientific article; zbMATH DE number 1445378 (Why is no real title available?)
• Improved bounds for the excluded-minor approximation of treedepth
• Computing Tree Decompositions
• scientific article; zbMATH DE number 7716293 (Why is no real title available?)
• An improved parameterized algorithm for treewidth
• Approximation algorithms for treewidth, pathwidth, and treedepth -- a short survey
• Approximation algorithms for treewidth

This page was built for publication: An improvement of Reed's treewidth approximation

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