Simple paths with exact and forbidden lengths

DOI10.1002/nav.21783zbMath1390.05084OpenAlexW2789557202MaRDI QIDQ4562938

Alexandre Dolgui, Alain Quilliot, Mikhail Y. Kovalyov

Publication date: 6 June 2018

Published in: Naval Research Logistics (NRL) (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

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

Related Items (1)

The vehicle routing problem with arrival time diversification on a multigraph

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Computing strictly-second shortest paths
• A quadratic algorithm for finding next-to-shortest paths in graphs
• Finding next-to-shortest paths in a graph
• Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications
• Improved algorithm for finding next-to-shortest paths
• Exact arborescences, matchings and cycles
• The directed subgraph homeomorphism problem
• Batch scheduling with deadlines on parallel machines
• Analysis of FPTASes for the multi-objective shortest path problem
• An improved FPTAS for Restricted Shortest Path.
• Knapsack problem with objective value gaps
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• The shortest route problem with constraints
• Accelerated label setting algorithms for the elementary resource constrained shortest path problem
• The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes
• Vehicle Routing
• Shortest chain subject to side constraints
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• The complexity of restricted spanning tree problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Maximum matching of given weight in complete and complete bipartite graphs
• Bicriterion Single Machine Scheduling with Resource Dependent Processing Times
• Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• Finding, minimizing, and counting weighted subgraphs
• STACS 2004
• Exact Weight Subgraphs and the k-Sum Conjecture
• A simple efficient approximation scheme for the restricted shortest path problem

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