Algorithmic applications of tree-cut width

DOI10.1007/978-3-662-48054-0_29zbMATH Open1465.68211OpenAlexW2403583756MaRDI QIDQ2946405FDOQ2946405

Authors: Robert Ganian, Eun Jung Kim, Stefan Szeider 

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

Recommendations

• Algorithmic applications of tree-cut width
• Cutwidth: obstructions and algorithmic aspects
• Cutwidth: obstructions and algorithmic aspects

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)

Cites Work

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

Cited In (22)

• Cutwidth: obstructions and algorithmic aspects
• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• A Menger-like property of tree-cut width
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Algorithmic applications of tree-cut width
• Slim tree-cut width
• The complexity landscape of decompositional parameters for ILP
• Packing and covering immersion models of planar subcubic graphs
• Title not available (Why is that?)
• On structural parameterizations of the bounded-degree vertex deletion problem
• Packing and covering immersion-expansions of planar sub-cubic graphs
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• Cutwidth: obstructions and algorithmic aspects
• The power of cut-based parameters for computing edge-disjoint paths
• Problems hard for treewidth but easy for stable gonality
• On objects dual to tree-cut decompositions
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On structural parameterizations of the bounded-degree vertex deletion problem
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs

This page was built for publication: Algorithmic applications of tree-cut width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946405)