Solving the replacement paths problem for planar directed graphs in O(n logn) time

Christian Wulff-Nilsen

doi:10.1137/1.9781611973075.62

Solving the replacement paths problem for planar directed graphs in O(n logn) time

Department of Computer Science

Abstract

In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linearspace algorithm with O(n log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n log2 n).

Original language	English
Title of host publication	Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms
Editors	Moses Charikar
Number of pages	10
Publisher	Society for Industrial and Applied Mathematics
Publication date	2010
Pages	756-765
ISBN (Print)	978-0-89871-701-3
ISBN (Electronic)	978-1-61197-307-5
DOIs	https://doi.org/10.1137/1.9781611973075.62
Publication status	Published - 2010
Event	21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, United States Duration: 17 Jan 2010 → 19 Jan 2010 Conference number: 21

Conference

Conference	21st Annual ACM-SIAM Symposium on Discrete Algorithms
Number	21
Country/Territory	United States
City	Austin
Period	17/01/2010 → 19/01/2010

Access to Document

10.1137/1.9781611973075.62

Cite this

Solving the replacement paths problem for planar directed graphs in O(n logn) time. / Wulff-Nilsen, Christian.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. ed. / Moses Charikar. Society for Industrial and Applied Mathematics, 2010. p. 756-765.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Wulff-Nilsen, C 2010, Solving the replacement paths problem for planar directed graphs in O(n logn) time. in M Charikar (ed.), Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, pp. 756-765, 21st Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, United States, 17/01/2010. https://doi.org/10.1137/1.9781611973075.62

@inproceedings{b9aa437023cf11df8ed1000ea68e967b,

title = "Solving the replacement paths problem for planar directed graphs in O(n logn) time",

abstract = "In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linearspace algorithm with O(n log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n log2 n).",

author = "Christian Wulff-Nilsen",

year = "2010",

doi = "10.1137/1.9781611973075.62",

language = "English",

isbn = "978-0-89871-701-3",

pages = "756--765",

editor = "Moses Charikar",

booktitle = "Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics",

address = "United States",

note = "21st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 ; Conference date: 17-01-2010 Through 19-01-2010",

}

TY - GEN

T1 - Solving the replacement paths problem for planar directed graphs in O(n logn) time

AU - Wulff-Nilsen, Christian

N1 - Conference code: 21

PY - 2010

Y1 - 2010

N2 - In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linearspace algorithm with O(n log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n log2 n).

AB - In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linearspace algorithm with O(n log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n log2 n).

U2 - 10.1137/1.9781611973075.62

DO - 10.1137/1.9781611973075.62

M3 - Article in proceedings

SN - 978-0-89871-701-3

SP - 756

EP - 765

BT - Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms

A2 - Charikar, Moses

PB - Society for Industrial and Applied Mathematics

T2 - 21st Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 17 January 2010 through 19 January 2010

ER -

Solving the replacement paths problem for planar directed graphs in O(n logn) time

Abstract

Conference

Access to Document

Fingerprint

Cite this