Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1347–1354, 2011.

Abstract:

Letsandtbe vertices in a directed graphGwith non-negative edge weights. The replacement paths problem asks us to compute, for each edgeeinG, the length of the shortest path fromstotthat does not traversee. We describe an algorithm that solves the replacement paths problem for directed graphs embedded on a surface of any genusgin O(gnlogn) time, generalizing a recent O(nlogn)-time algorithm of Wulff-Nilsen for planar graphs [SODA 2010].

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 21 Jan 2012