Slim tree-cut width

DOI10.4230/LIPICS.IPEC.2022.15MaRDI QIDQ6968997zbMATH OpenFDO

Authors Robert Ganian, Viktoriia Korchemna

Publication date 23 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2022.15

zbMATH Keywords

graph immersionsstructural parameterstree-cut width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A Menger-like property of tree-cut width
• Algorithmic applications of tree-cut width
• An FPT 2-approximation for tree-cut decomposition
• Boolean-width of graphs
• Constraint satisfaction with bounded treewidth revisited
• Constructing minimum changeover cost arborescenses in bounded treewidth graphs
• Edge-cut width: an algorithmically driven analogue of treewidth based on edge cuts
• Fundamentals of parameterized complexity
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. II. Algorithmic aspects of tree-width
• Graph-Theoretic Concepts in Computer Science
• Hamiltonian cycle parameterized by treedepth in single exponential time and polynomial space
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• Immersions in highly edge connected graphs
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Linear time solvable optimization problems on graphs of bounded clique-width
• New algorithms for maximum disjoint paths based on tree-likeness
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• On structural parameterizations of the bounded-degree vertex deletion problem
• On structural parameterizations of the edge disjoint paths problem
• Parameterized algorithms
• Parameterized algorithms for stable matching with ties and incomplete lists
• Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
• Parameterized complexity of the MinCCA problem on graphs of bounded decomposability
• Parameterized complexity results for exact Bayesian network structure learning
• Preprocessing for treewidth: a combinatorial analysis through kernelization
• Sparsity. Graphs, structures, and algorithms
• The complexity landscape of decompositional parameters for ILP
• The firefighter problem for graphs of maximum degree three
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• The power of cut-based parameters for computing edge-disjoint paths
• The structure of graphs not admitting a fixed immersion
• Towards a polynomial kernel for directed feedback vertex set
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter

Cited in

(1)

• The parameterized complexity landscape of the unsplittable flow problem

This page was built for publication: Slim tree-cut width

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