| Article ID: | iaor2006320 |
| Country: | Netherlands |
| Volume: | 33 |
| Issue: | 5 |
| Start Page Number: | 459 |
| End Page Number: | 466 |
| Publication Date: | Sep 2005 |
| Journal: | Operations Research Letters |
| Authors: | Bhosle Amit M. |
| Keywords: | networks: path |
We present near-optimal algorithms for two problems related to finding the replacement paths for edges with respect to shortest paths in sparse graphs. The problems essentially study how the shortest paths change as edges on the path fail, one at a time. Our technique improves the existing bounds for these problems on directed acrylic graphs, planar graphs, and non-planar integer-edge-weighted graphs.