Return to search

Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/5065
Date30 April 2004
CreatorsRamaswamy, Ramkumar, Orlin, James B., Chakravarty, Nilopal
Source SetsM.I.T. Theses and Dissertation
Languageen_US
Detected LanguageEnglish
TypeWorking Paper
Format504845 bytes, application/pdf
RelationMIT Sloan School of Management Working Paper;4465-03

Page generated in 0.0023 seconds