Simple paths with exact and forbidden lengths

DOI10.1002/NAV.21783MaRDI QIDQ4562938zbMATH OpenOpenAlexFDO

Authors Alexandre Dolgui, M. Y. Kovalyov, Alain Quilliot

Publication date 6 June 2018

Published in Naval Research Logistics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/nav.21783

zbMATH Keywords

computational complexityapproximationshortest path problemlongest path problemexact path lengthforbidden path length

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Signed and weighted graphs (05C22) Paths and cycles (05C38) Communication networks in operations research (90B18)

Recommendations

• The exact path length problem.
• A note on shortest path problems with forbidden paths
• scientific article; zbMATH DE number 3876620
• Algorithms for finding paths with multiple constraints
• On the complexity of vertex-disjoint length-restricted path problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A quadratic algorithm for finding next-to-shortest paths in graphs
• A simple efficient approximation scheme for the restricted shortest path problem
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• An improved FPTAS for Restricted Shortest Path.
• Analysis of FPTASes for the multi-objective shortest path problem
• Approximation Schemes for the Restricted Shortest Path Problem
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Batch scheduling with deadlines on parallel machines
• Bicriterion Single Machine Scheduling with Resource Dependent Processing Times
• Computing strictly-second shortest paths
• Exact arborescences, matchings and cycles
• Exact weight subgraphs and the k-sum conjecture
• Finding next-to-shortest paths in a graph
• Finding, minimizing, and counting weighted subgraphs
• Improved algorithm for finding next-to-shortest paths
• Introduction to algorithms.
• Knapsack problem with objective value gaps
• Maximum matching of given weight in complete and complete bipartite graphs
• Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications
• Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality
• STACS 2004
• Shortest chain subject to side constraints
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• The complexity of restricted spanning tree problems
• The directed subgraph homeomorphism problem
• The exact weighted independent set problem in perfect graphs and related classes
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• The shortest route problem with constraints
• Vehicle Routing

Cited in

(5)

• The exact path length problem.
• On the length of simplex paths: The assignment case
• The vehicle routing problem with arrival time diversification on a multigraph
• Simple Paths and Cycles Avoiding Forbidden Paths
• On the computational complexity of length- and neighborhood-constrained path problems

Describes a project that uses

Uses Software

• VRP

This page was built for publication: Simple paths with exact and forbidden lengths

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