Network reduction for the acyclic constrained shortest path problem (Q1206607)

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.