Parameterized complexity of length-bounded cuts and multicuts

DOI10.1007/s00453-018-0408-7zbMath1400.90258arXiv1511.02801OpenAlexW2952915478MaRDI QIDQ1799212

Pavel Dvořák, Dušan Knop

Publication date: 18 October 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.02801

zbMATH Keywords

parameterized algorithmstree-widthpolynomial kerneltree-depthlength-bounded cuts\(\mathsf{W}[1\)-hardness]

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Distance in graphs (05C12)

Related Items (10)

Length-bounded cuts: proper interval graphs and structural parameters ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Fine-grained parameterized complexity analysis of graph coloring problems

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• On problems without polynomial kernels
• Treewidth. Computations and approximations
• On the directed hop-constrained shortest path problem
• The complexity landscape of decompositional parameters for ILP
• Tree-depth, subgraph coloring and homomorphism bounds
• Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
• Length-bounded cuts and flows
• Maximal Flow Through a Network
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Structural Parameterizations of the Mixed Chinese Postman Problem
• Capacitated Domination and Covering: A Parameterized Perspective
• Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
• The complexity of finding maximum disjoint paths with length constraints
• Max flows in O(nm) time, or better
• Parameterized Algorithms
• A Theorem on Boolean Matrices

This page was built for publication: Parameterized complexity of length-bounded cuts and multicuts