Algorithmic Applications of Tree-Cut Width
From MaRDI portal
Publication:5048301
DOI10.1137/20M137478XzbMath1503.05117arXiv2206.00752OpenAlexW4308732512MaRDI QIDQ5048301
Robert Ganian, Stefan Szeider, Eun Jung Kim
Publication date: 15 November 2022
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2206.00752
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Linear programming (90C05) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- The structure of graphs not admitting a fixed immersion
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Distributed approximation of capacitated dominating sets
- On the complexity of some colorful problems parameterized by treewidth
- Constraint satisfaction with bounded treewidth revisited
- Clean the graph before you draw it!
- An application of simultaneous diophantine approximation in combinatorial optimization
- Precoloring extension. I: Interval graphs
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- Treewidth. Computations and approximations
- Complexity of list coloring problems with a fixed total number of colors
- Which problems have strongly exponential complexity?
- An FPT 2-approximation for tree-cut decomposition
- Balanced vertex-orderings of graphs
- Graph minors. XIII: The disjoint paths problem
- On structural parameterizations of the bounded-degree vertex deletion problem
- Imbalance is fixed parameter tractable
- Parameterized complexity of Vertex Cover variants
- Parametrized complexity theory.
- Tree-depth, subgraph coloring and homomorphism bounds
- The power of cut-based parameters for computing edge-disjoint paths
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Integer Programming with a Fixed Number of Variables
- Capacitated Domination and Covering: A Parameterized Perspective
- Graph Layout Problems Parameterized by Vertex Cover
- Planar Capacitated Dominating Set Is W[1-Hard]
- Minkowski's Convex Body Theorem and Integer Programming
- Capacitated vertex covering
- Immersions in Highly Edge Connected Graphs
- SAT-Encodings for Treecut Width and Treedepth
- NP‐completeness of list coloring and precoloring extension on the edges of planar graphs
- Finding topological subgraphs is fixed-parameter tractable
- Parameterized Algorithms
- Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
This page was built for publication: Algorithmic Applications of Tree-Cut Width
