Network reduction for the acyclic constrained shortest path problem (Q1206607)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Network reduction for the acyclic constrained shortest path problem |
scientific article |
Statements
Network reduction for the acyclic constrained shortest path problem (English)
0 references
1 April 1993
0 references
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.
0 references
shortest path
0 references
transportation
0 references
acyclic digraph
0 references
0 references