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...
| Main Authors: | , , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/7389 |
| _version_ | 1811087034301808640 |
|---|---|
| author | Ramaswamy, Ramkumar Orlin, James Chakravarty, Nilopal |
| author_facet | Ramaswamy, Ramkumar Orlin, James Chakravarty, Nilopal |
| author_sort | Ramaswamy, Ramkumar |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:38:28Z |
| format | Working Paper |
| id | mit-1721.1/7389 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:38:28Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/73892019-04-12T09:32:14Z Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs Ramaswamy, Ramkumar Orlin, James Chakravarty, Nilopal sensitivity analysis shortest path problem bottleneck shortest path maximum capacity path problem 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. 2004-12-10T19:14:11Z 2004-12-10T19:14:11Z 2004-12-10T19:14:11Z Working Paper http://hdl.handle.net/1721.1/7389 en_US MIT Sloan School of Management Working Paper;4465-03 504845 bytes application/pdf application/pdf |
| spellingShingle | sensitivity analysis shortest path problem bottleneck shortest path maximum capacity path problem Ramaswamy, Ramkumar Orlin, James Chakravarty, Nilopal Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs |
| title | Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs |
| title_full | Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs |
| title_fullStr | Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs |
| title_full_unstemmed | Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs |
| title_short | Sensitivity Analysis for Shortest Path Problems and Maximum Capacity Path Problems in Undirected Graphs |
| title_sort | sensitivity analysis for shortest path problems and maximum capacity path problems in undirected graphs |
| topic | sensitivity analysis shortest path problem bottleneck shortest path maximum capacity path problem |
| url | http://hdl.handle.net/1721.1/7389 |
| work_keys_str_mv | AT ramaswamyramkumar sensitivityanalysisforshortestpathproblemsandmaximumcapacitypathproblemsinundirectedgraphs AT orlinjames sensitivityanalysisforshortestpathproblemsandmaximumcapacitypathproblemsinundirectedgraphs AT chakravartynilopal sensitivityanalysisforshortestpathproblemsandmaximumcapacitypathproblemsinundirectedgraphs |