On the complexity of vertex-disjoint length-restricted path problems

DOI10.1007/S00037-003-0179-6MaRDI QIDQ1762664zbMATH OpenOpenAlexFDO

Authors Andreas Bley

Publication date 11 February 2005

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-003-0179-6

zbMATH Keywords

approximabilityDisjoint pathslength-restricted paths

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 47435
• On the complexity of the disjoint paths problem
• scientific article; zbMATH DE number 4191702
• On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems
• On the complexity of the planar directed edge-disjoint paths problem
• Complexity and approximation results for the min-sum and min-max disjoint paths problems
• On the computational complexity of length- and neighborhood-constrained path problems
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

Cited in

(21)

• On vertex-degree restricted paths in polyhedral graphs
• On the computational complexity of length- and neighborhood-constrained path problems
• Two edge-disjoint paths with length constraints
• On the complexity of the disjoint paths problem
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• On b-acyclic chromatic number of a graph
• OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
• The Complexity of Restricted Variants of the Stable Paths Problem
• Length-constrained path-matchings in graphs
• Finding two edge-disjoint paths with length constraints
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Heuristics for finding a maximum number of disjoint bounded paths
• On the length of simplex paths: The assignment case
• On the maximum disjoint paths problem on edge-colored graphs
• Length 3 edge-disjoint paths is NP-hard
• Simple paths with exact and forbidden lengths
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Short length Menger's theorem and reliable optical routing
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• Maximum \(k\)-splittable \(s, t\)-flows

This page was built for publication: On the complexity of vertex-disjoint length-restricted path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1762664)