Maximizing the minimum source-sink path subject to a budget constraint

Given a linear cost function for lengthening arcs, a technique is shown for maximizing, within a budget, the shortest source—sink path length in a graph. The computation is equivalent to the parametric solution of a minimum cost flow problem.This work was done while G.C. Harding was at Cornell University.The work of D.R. Fulkerson was supported by the National Science Foundation under Grant MPS74-24026 and by the Office of Naval Research under Grant NR 044-439.