Abstract
Let s and t be vertices in a directed graph G with non-negative edge weights. The replacement paths problem asks us to compute, for each edge e in G, the length of the shortest path from s to t that does not traverse e. We describe an algorithm that solves the replacement paths problem for directed graphs embedded on a surface of any genus g in O(gn log n) time, generalizing a recent O(n log n)-time algorithm of Wulff-Nilsen for planar graphs [SODA 2010].
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 |
| Pages | 1347-1354 |
| Number of pages | 8 |
| State | Published - 2011 |
| Event | 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 - San Francisco, CA, United States Duration: Jan 23 2011 → Jan 25 2011 |
Other
| Other | 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 |
|---|---|
| Country | United States |
| City | San Francisco, CA |
| Period | 1/23/11 → 1/25/11 |
Fingerprint
ASJC Scopus subject areas
- Software
- Mathematics(all)
Cite this
Erickson, J. G., & Nayyeri, A. (2011). Computing replacement paths in surface embedded graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 (pp. 1347-1354)