H-TD computes a width-3 tree decomposition of any Halin graph in linear time, and its C++ prototype outperforms PACE 2017 solvers and libtw on Halin instances.
Computing bounded-width tree and branch decompositions of k-outerplanar graphs
1 Pith paper cite this work, alongside 1 external citations. Polarity classification is still indexing.
1
Pith paper citing it
1
external citations · Pith
abstract
By a well known result the treewidth of k-outerplanar graphs is at most 3k-1. This paper gives, besides a rigorous proof of this fact, an algorithmic implementation of the proof, i.e. it is shown that, given a k-outerplanar graph G, a tree decomposition of G of width at most 3k-1 can be found in O(kn) time and space. Similarly, a branch decomposition of a k-outerplanar graph of width at most 2k+1 can be also obtained in O(kn) time, the algorithm for which is also analyzed.
citation-role summary
baseline 1
citation-polarity summary
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1roles
baseline 1polarities
support 1representative citing papers
citing papers explorer
-
A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
H-TD computes a width-3 tree decomposition of any Halin graph in linear time, and its C++ prototype outperforms PACE 2017 solvers and libtw on Halin instances.