Abstract :
A network with vertices 1; …, n in which each arc has the form (i, j) with i < j is considered. Under the assumption that the distances satisfy certain monotonicity assumptions O(n)-algorithms for calculating shortest and min-max paths from 1 to n are presented. Applications to one-machine batching, clustering, and image processing are indicated.
