Computing replacement paths in surface embedded graphs

Jeff G Erickson, Amir Nayyeri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
Pages1347-1354
Number of pages8
StatePublished - 2011
Event22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011 - San Francisco, CA, United States
Duration: Jan 23 2011Jan 25 2011

Other

Other22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
CountryUnited States
CitySan Francisco, CA
Period1/23/111/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)