Standard
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. red. / Moses Charikar. Society for Industrial and Applied Mathematics, 2010. s. 756-765.
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
Wulff-Nilsen, C 2010,
Solving the replacement paths problem for planar directed graphs in O(n logn) time. i M Charikar (red.),
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, s. 756-765, 21st Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, USA,
17/01/2010.
https://doi.org/10.1137/1.9781611973075.62
APA
Wulff-Nilsen, C. (2010).
Solving the replacement paths problem for planar directed graphs in O(n logn) time. I M. Charikar (red.),
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (s. 756-765). Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611973075.62
Vancouver
Wulff-Nilsen C.
Solving the replacement paths problem for planar directed graphs in O(n logn) time. I Charikar M, red., Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics. 2010. s. 756-765
https://doi.org/10.1137/1.9781611973075.62
Author
Wulff-Nilsen, Christian. / Solving the replacement paths problem for planar directed graphs in O(n logn) time. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms. red. / Moses Charikar. Society for Industrial and Applied Mathematics, 2010. s. 756-765
Bibtex
@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",
}
RIS
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 -
