← all papers Β· overview

Optimized 2-Approximation of Treewidth

Abstract

This paper presents a linear FPT algorithm to find a tree decomposition with a 2-approximation of the treewidth with a significantly smaller exponential dependence on the treewidth. The algorithm runs in time $O(\text{poly}(k) 81^k n)$, compared to Korhonen's running time of $O(\text{poly}(k) 1782^k n)$ = $O(2^{10.8k} n)$.

Related papers

Ranked by semantic similarity β€” how closely each paper's abstract matches this one (100% = near-identical topic).