Algorithmic applications of tree-cut width

DOI10.1007/978-3-662-48054-0_29MaRDI QIDQ2946405zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

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

Cited in

(26)

• Cutwidth: obstructions and algorithmic aspects
• The complexity landscape of decompositional parameters for ILP
• 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
• Packing and covering immersion-expansions of planar sub-cubic graphs
• The power of cut-based parameters for computing edge-disjoint paths
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• Packing and covering immersion models of planar subcubic graphs
• On structural parameterizations of the bounded-degree vertex deletion problem
• scientific article; zbMATH DE number 1066875 (Why is no real title available?)
• scientific article; zbMATH DE number 1944139 (Why is no real title available?)
• scientific article; zbMATH DE number 1760009 (Why is no real title available?)
• Cutwidth: obstructions and algorithmic aspects
• Algorithmic applications of tree-cut width
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Problems hard for treewidth but easy for stable gonality
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• scientific article; zbMATH DE number 7765417 (Why is no real title available?)
• Slim tree-cut width
• Slim tree-cut width
• On the parameterized complexity of computing tree-partitions
• On the parameterized complexity of computing tree-partitions
• A metrization theorem for edge-end spaces of infinite 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)