An FPT 2-approximation for tree-cut decomposition

DOI10.1007/s00453-016-0245-5zbMath1386.68221arXiv1509.04880OpenAlexW2761665840MaRDI QIDQ1702123

Sang-il Oum, Christophe Paul, Dimitrios M. Thilikos, Eun Jung Kim, Ignasi Sau

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

zbMATH Keywords

approximation algorithmfixed-parameter tractable algorithmtree-cut width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (15)

Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Parameterized complexity of the MinCCA problem on graphs of bounded decomposability ⋮ On objects dual to tree-cut decompositions ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ A Menger-like property of tree-cut width ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Cites Work

• Paths of bounded length and their cuts: parameterized complexity and algorithms
• The structure of graphs not admitting a fixed immersion
• On the complexity of some colorful problems parameterized by treewidth
• Graph minors. III. Planar tree-width
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Graph minors. V. Excluding a planar graph
• Graph searching and a min-max theorem for tree-width
• Call routing and the ratcatcher
• Treewidth. Computations and approximations
• An FPT 2-approximation for tree-cut decomposition
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Algorithmic Applications of Tree-Cut Width
• Capacitated Domination and Covering: A Parameterized Perspective
• Constructive algorithm for path-width of matroids
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Parameterized and Exact Computation
• Bidimensionality and Geometric Graphs
• Finding topological subgraphs is fixed-parameter tractable
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An FPT 2-approximation for tree-cut decomposition