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.
scientific article; zbMATH DE number 149249