| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10524006 | Operations Research Letters | 2005 | 8 Pages |
Abstract
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 acyclic graphs, planar graphs, and non-planar integer-edge-weighted graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Amit M. Bhosle,