An FPT 2-approximation for tree-cut decomposition
From MaRDI portal
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
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
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
