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|
|Publisher||Association for Computing Machinery|
|Number of pages||8|
|State||Published - 2011|
|Name||Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms|
ASJC Scopus subject areas