Shortest Path Problems:A Parametric Study

  • Lee, In-Soo (Department of Management Science, Korea Advanced Institute of Science and Technology)
  • Published : 1991.12.01

Abstract

Two important sensitivity issues over shortest path problems have been discussed. One is the problem of updating shortest paths when nodes are added and when the lengths of some arcs are increased or decreased. The other is the problem of calculating arc tolerances, that is the maximum increase of decrease in the length of a single arc without changing a given optimal tree. In this paper, assuming that there exists a parameter of interest whose perturbation causes the simultaneous changes in arc lengths, we find the invariance condition on these simultaneous changes such that the shortest path between two specified nodes remains unchanged.

Keywords

References

  1. Operations Research v.32 Determining all optimal and near optimal solutions when solving shortest path problems by dynamic programming Byers,T.H.;Waterman,M.S.
  2. Dynamic Programming : Models and Application Denardo,E.V.
  3. Operations Research v.27 Shortest-route methods : 1. reaching, pruning, and buckets Denardo,E.V.;Fox,B.L.
  4. Operations Research v.17 An appraisal of some shortest-path algorithms Dreyfus,S.E.
  5. Operation Research v.21 Sequencing expansion projects Erlenketter,D.
  6. Networks v.11 A note on the problem of updating shortest paths Fujishige,S.
  7. Networks v.8 A new shortest path updating algoritgm Goto,S.;Sangiovanni-Vincentelli, A.
  8. Networks v.13 A note on arc tolerances in sparse shortest-path and network flow problems Gusfield,D.
  9. J. of Korean OR/MS Society v.12 Sensitivity analysis for production planning problems with backlogging Lee,I.S.
  10. J. of Korean OR/MS Society v.13 Sensitivity analysis of project sequencing problems Lee,I.S.
  11. U.S.S.R. Compluational Mathematics and Mathematical Physics v.8 The parametric problem of shortest distances Rodionov,V.
  12. Networks v.10 Arc tolerances in shortest path and network flow algorithms Shier,D.R.;Witzgall,G.
  13. SIAM J. Computing v.4 On finding and updating spanning trees and shortest paths Spira,P.M.;Pan,A.
  14. Information Processing Letters v.14 Sensitivity analysis of minimum spanning trees and shortest path trees Tarjan,R.E.
  15. Principles of Operation Research(2nd ed.) Wagner,H.M.
  16. Management Science v.13 A deterministic multiperiod production scheduling model with backloggong Zangwill,W.L.