Approximating Pathwidth for Graphs of Small Treewidth

DOI10.1145/3576044arXiv2008.00779OpenAlexW3046743316MaRDI QIDQ6075751

Wojciech Nadara, Gwenaël Joret, Carla Groenland, Bartosz Walczak

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.00779

zbMATH Keywords

treewidthpathwidth

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple linear-time algorithm for finding path-decompositions of small width
• Graph minors. V. Excluding a planar graph
• Min Cut is NP-complete for edge weighted trees
• Quickly excluding a forest
• On the pathwidth of chordal graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• A polynomial excluded-minor approximation of treedepth
• Towards tight(er) bounds for the excluded grid theorem
• Fixed-Parameter Tractability of Treewidth and Pathwidth
• Approximation of pathwidth of outerplanar graphs
• Polynomial Bounds for the Grid-Minor Theorem
• Connected Treewidth and Connected Graph Searching
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Complexity of Finding Embeddings in a k-Tree
• Three results for trees, using mathematical induction
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Improved Bounds for the Excluded-Minor Approximation of Treedepth
• Circumference and Pathwidth of Highly Connected Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A 3-approximation for the pathwidth of Halin graphs

This page was built for publication: Approximating Pathwidth for Graphs of Small Treewidth