Paths of bounded length and their cuts: parameterized complexity and algorithms

DOI10.1016/j.disopt.2010.09.009zbMath1248.90071OpenAlexW2050719228MaRDI QIDQ456699

Dimitrios M. Thilikos, Petr A. Golovach

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.09.009

zbMATH Keywords

parameterized algorithmsparameterized complexitybounded length cutsbounded length disjoint paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Length-bounded cuts: proper interval graphs and structural parameters ⋮ Finding disjoint paths on edge-colored graphs: more tractability results ⋮ Finding Two Edge-Disjoint Paths with Length Constraints ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ A constraint programming approach to the additional relay placement problem in wireless sensor networks ⋮ An FPT 2-approximation for tree-cut decomposition ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Fractals for Kernelization Lower Bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Confronting intractability via parameters ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ A Flexible, Natural Formulation for the Network Design Problem with Vulnerability Constraints ⋮ On Algorithms Employing Treewidth for $L$-bounded Cut Problems ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs ⋮ The complexity of finding small separators in temporal graphs ⋮ Parameterized complexity of length-bounded cuts and multicuts ⋮ Two edge-disjoint paths with length constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of finding two disjoint paths with min-max objective function
• On miniaturized problems in parameterized complexity theory
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• The directed subgraph homeomorphism problem
• Mengerian theorems for paths of bounded length
• A special planar satisfiability problem and a consequence of its NP- completeness
• On the complexity of vertex-disjoint length-restricted path problems
• On line disjoint paths of bounded length
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Graph minors. XIII: The disjoint paths problem
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• Length-bounded cuts and flows
• Maximal Flow Through a Network
• Easy problems for tree-decomposable graphs
• Improved bounds for the unsplittable flow problem
• Capacitated Domination and Covering: A Parameterized Perspective
• Length-Bounded Cuts and Flows
• Planar Capacitated Dominating Set Is W[1-Hard]
• Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
• Heuristics for finding a maximum number of disjoint bounded paths
• On the Computational Complexity of Combinatorial Problems
• Color-coding
• The complexity of finding maximum disjoint paths with length constraints
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems