Paths of bounded length and their cuts: parameterized complexity and algorithms
From MaRDI portal
Publication:456699
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
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
