@inproceedings{01622625004647fe933d039f2ffe5b5a,
title = "Computing replacement paths in surface embedded graphs",
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].",
author = "Jeff Erickson and Amir Nayyeri",
year = "2011",
doi = "10.1137/1.9781611973082.103",
language = "English (US)",
isbn = "9780898719932",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "1347--1354",
booktitle = "Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011",
address = "United States",
}