An FPT 2-Approximation for Tree-cut Decomposition - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2015

An FPT 2-Approximation for Tree-cut Decomposition

Abstract

The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47–66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input n-vertex graph G and an integer w, our algorithm either confirms that the tree-cut width of G is more than w or […]

Dates and versions

lirmm-01264015 , version 1 (28-01-2016)

Identifiers

Cite

Eun Jung Kim, Sang-Il Oum, Christophe Paul, Ignasi Sau, Dimitrios M. Thilikos. An FPT 2-Approximation for Tree-cut Decomposition. WAOA 2015 - 13th International Workshop on Approximation and Online Algorithms, Sep 2015, Patras, Greece. pp.35-46, ⟨10.1007/978-3-319-28684-6_4⟩. ⟨lirmm-01264015⟩
173 View
0 Download

Altmetric

Share

More