Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
From MaRDI portal
Publication:3656863
DOI10.1007/978-3-642-11269-0_17zbMath1273.68172OpenAlexW1875643871MaRDI QIDQ3656863
Dimitrios M. Thilikos, Petr A. Golovach
Publication date: 14 January 2010
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_17
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ Confronting intractability via parameters
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 the parameterized complexity of multiple-interval graph problems
- The directed subgraph homeomorphism problem
- Mengerian theorems for paths of bounded length
- 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
- Parametrized complexity theory.
- Length-bounded cuts and flows
- Maximal Flow Through a Network
- Easy problems for tree-decomposable graphs
- Improved bounds for the unsplittable flow problem
- On Problems without Polynomial Kernels (Extended Abstract)
- Length-Bounded Cuts and Flows
- 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
This page was built for publication: Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
