An FPT 2-approximation for tree-cut decomposition
From MaRDI portal
Publication:1702123
DOI10.1007/s00453-016-0245-5zbMath1386.68221arXiv1509.04880MaRDI QIDQ1702123
Christophe Paul, Sang-il Oum, Ignasi Sau, Dimitrios M. Thilikos, Eun Jung Kim
Publication date: 28 February 2018
Published in: Algorithmica, Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.04880
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Parameterized algorithms for min-max multiway cut and list digraph homomorphism, Parameterized complexity of the MinCCA problem on graphs of bounded decomposability, Algorithmic Applications of Tree-Cut Width