Maximizing the Minimum Source-Sink Path Subject to a Budget Constraint: Another View of the Minimum Cost Flow Routine.

摘要

Consider a network in which each arc has a traversal time and a cost for increasing its traversal time. If a fixed budget is available for expenditure on arcs of the network, how does one allocate this budget among the arcs so as to maximize the length of a shortest path from source to sink. It is shown that the minimum cost flow algorithm can be used to solve this problem parametrically in the budget.