Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time
Research output: Working paper › Research
Standard
Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time. / Wulff-Nilsen, Christian.
København : Datalogisk Institut, 2009. p. 1-21.Research output: Working paper › Research
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - UNPB
T1 - Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time
AU - Wulff-Nilsen, Christian
PY - 2009
Y1 - 2009
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 linear-space algorithm with O(nlog n) running time for n-vertex planar directed graphs. The previous best time bound was O(n(log n)^2).
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 linear-space algorithm with O(nlog n) running time for n-vertex planar directed graphs. The previous best time bound was O(n(log n)^2).
M3 - Working paper
SP - 1
EP - 21
BT - Solving the Replacement Paths Problem for Planar Directed Graphs in O(nlog n) Time
PB - Datalogisk Institut
CY - København
ER -
ID: 12874195