Suppose we are given a network G=(V,E) with arc distances and a linear cost function for lengthening arcs. In this note, we consider a network‐interdiction problem in which the shortest path from source node s to sink node t is to be increased to at least τ units via a least‐cost investment strategy. This problem is shown to reduce to a simple minimum‐cost‐flow problem. Applications and generalizations are discussed, including the multiple‐destination case.
No takes yet. Share an insight, caveat, or question.
Bruce Golden (1978) studied this question.