Algorithmic Applications of Tree-Cut Width

DOI10.1007/978-3-662-48054-0_29zbMath1465.68211OpenAlexW2403583756MaRDI QIDQ2946405

Stefan Szeider, Eun Jung Kim, Robert Ganian

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_29

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (17)

Packing and Covering Immersion Models of Planar Subcubic Graphs ⋮ Parameterized complexity of the MinCCA problem on graphs of bounded decomposability ⋮ Packing and covering immersion-expansions of planar sub-cubic graphs ⋮ 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 ⋮ Problems hard for treewidth but easy for stable gonality ⋮ 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 ⋮ Unnamed Item ⋮ On structural parameterizations of the bounded-degree vertex deletion problem ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ The complexity landscape of decompositional parameters for ILP ⋮ A Menger-like property of tree-cut width ⋮ Lean Tree-Cut Decompositions: Obstructions and Algorithms ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• The structure of graphs not admitting a fixed immersion
• On the complexity of some colorful problems parameterized by treewidth
• Constraint satisfaction with bounded treewidth revisited
• An application of simultaneous diophantine approximation in combinatorial optimization
• Precoloring extension. I: Interval graphs
• Treewidth. Computations and approximations
• An FPT 2-approximation for tree-cut decomposition
• Balanced vertex-orderings of graphs
• Imbalance is fixed parameter tractable
• Tree-depth, subgraph coloring and homomorphism bounds
• Integer Programming with a Fixed Number of Variables
• Capacitated Domination and Covering: A Parameterized Perspective
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. II. Algorithmic aspects of tree-width
• Minkowski's Convex Body Theorem and Integer Programming
• Immersions in Highly Edge Connected Graphs
• Finding topological subgraphs is fixed-parameter tractable

This page was built for publication: Algorithmic Applications of Tree-Cut Width