Premium
Arc tolerances in shortest path and network flow problems
Author(s) -
Shier D. R.,
Witzgall Christoph
Publication year - 1980
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230100402
Subject(s) - arc (geometry) , shortest path problem , robustness (evolution) , arc length , mathematical optimization , path (computing) , flow network , computer science , flow (mathematics) , mathematics , simple (philosophy) , algorithm , topology (electrical circuits) , theoretical computer science , geometry , combinatorics , graph , chemistry , philosophy , epistemology , gene , biochemistry , programming language
Abstract This paper studies one aspect of the “robustness” of optimal solutions to shortest path and, more generally, network flow problems. Specifically, we characterize the maximum increase and the maximum decrease in an arc's cost that can be tolerated without changing optimality of the current solution. Calculation of these quantities is quite simple for nonbasic arcs, and somewhat more involved for basic arcs. When such tolerances are to be determined simultaneously for all arcs in the network, considerable duplication of effort can be avoided through the use of specialized algorithms. Several algorithms for calculating all arc tolerances are presented, one of which is shown to have complexity order n 2 for general networks with n nodes.