TY - GEN
T1 - Computing replacement paths in surface embedded graphs
AU - Erickson, Jeff
AU - Nayyeri, Amir
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2011
Y1 - 2011
N2 - 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].
AB - 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].
UR - http://www.scopus.com/inward/record.url?scp=79955745818&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79955745818&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973082.103
DO - 10.1137/1.9781611973082.103
M3 - Conference contribution
AN - SCOPUS:79955745818
SN - 9780898719932
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 1347
EP - 1354
BT - Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
PB - Association for Computing Machinery
ER -