Length-bounded cuts: proper interval graphs and structural parameters

DOI10.1016/j.jcss.2021.12.002zbMath1505.68032arXiv1910.03409OpenAlexW2979496305MaRDI QIDQ2119399

Matthias Bentert, Klaus Heeger, Dušan Knop

Publication date: 29 March 2022

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

pathwidthedge-disjoint pathsfeedback vertex number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Grundy Distinguishes Treewidth from Pathwidth ⋮ A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On the parameterized complexity of multiple-interval graph problems
• Hop-constrained node survivable network design: An application to MPLS over WDM
• An \(O(IVI^3)\) algorithm for finding maximum flows in networks
• Which problems have strongly exponential complexity?
• Parameterized complexity of length-bounded cuts and multicuts
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth
• Length-bounded cuts and flows
• Maximal Flow Through a Network
• Improved bounds for the unsplittable flow problem
• The two-edge connected hop-constrained network design problem: Valid inequalities and branch-and-cut
• Integer programming formulations for the two 4-hop-constrained paths problem
• Graph Classes: A Survey
• Fractals for Kernelization Lower Bounds
• A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths
• On Algorithms Employing Treewidth for $L$-bounded Cut Problems
• Parameterized Algorithms
• On the complexity of \(k\)-SAT
• Parameterized Complexity of Geodetic Set

This page was built for publication: Length-bounded cuts: proper interval graphs and structural parameters