Computing replacement paths in surface embedded graphs

Jeff Erickson; Amir Nayyeri

doi:10.1137/1.9781611973082.103

Computing replacement paths in surface embedded graphs

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 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
Pages	1347-1354
Number of pages	8
ISBN (Print)	9780898719932
DOIs	https://doi.org/10.1137/1.9781611973082.103
State	Published - 2011

Publication series

Name	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

ASJC Scopus subject areas

Software
Mathematics(all)

Access to Document

10.1137/1.9781611973082.103

Fingerprint Dive into the research topics of 'Computing replacement paths in surface embedded graphs'. Together they form a unique fingerprint.

Cite this

Computing replacement paths in surface embedded graphs. / Erickson, Jeff; Nayyeri, Amir.

Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011. Association for Computing Machinery, 2011. p. 1347-1354 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

@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",

}

TY - GEN

T1 - Computing replacement paths in surface embedded graphs

AU - Erickson, Jeff

AU - Nayyeri, Amir

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 -