An FPT 2-approximation for tree-cut decomposition

DOI10.1007/s00453-016-0245-5zbMath1386.68221arXiv1509.04880MaRDI 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 algorithm; fixed-parameter tractable algorithm; tree-cut width

Mathematics Subject Classification ID

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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