Network reduction for the acyclic constrained shortest path problem
The paper is about minimizing the length \(d(P)\) of a path \(P\) from a source \(r\) to a sink \(t\) in an acyclic digraph \(G\); moreover, \(P\) must be admissible, i.e. the time \(t(P)\) caused by the path \(P\) must not exceed a fixed limit \(T\). The main idea is to reduce the given graph by removing nodes \(v\) and arcs \(a\) which cannot be visited by any admissibe path; a typical case is that \(t(P')>T\) for all paths \(P'\) from \(r\) to \(v\). The author gives several situations in which \(v\) or \(a\) can be deleted, and he describes some practical tests of this method.
- A bicriterion shortest path algorithm
- A note on two problems in connexion with graphs
- Computational experience with an algorithm for finding the k shortest paths in a network
- Improved convexity cuts for lattice point problems
- Note on Multiple Objective Dynamic Programming
- On a multicriteria shortest path problem
- Shortest-path algorithms: Taxonomy and annotation
- Solving k-shortest and constrained shortest path problems efficiently
- The constrained shortest path problem
- The shortest path problem with two objective functions
- The shortest route problem with constraints
This page was built for publication: Network reduction for the acyclic constrained shortest path problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1206607)
