Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms

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

zbMATH Keywords

parameterized algorithmsparameterized complexitybounded length cutsbounded length disjoint paths

Mathematics Subject Classification ID

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