Korteste Veje i Planare Grafer med Reelle Kantvægte i O(n(log n)^2/loglog n) Tid

TY - UNPB

T1 - Korteste Veje i Planare Grafer med Reelle Kantvægte i O(n(log n)^2/loglog n) Tid

AU - Wulff-Nilsen, Christian

PY - 2009

Y1 - 2009

N2 - Given an n-vertex planar directed graph with real edge lengths and with no negative cycles, we show how to compute single-source shortest path distances in the graph in O(n(log n)^2/loglog n) time with O(n) space. This is an improvement of a recent time bound of O(n(log n)^2) by Klein et al.

AB - Given an n-vertex planar directed graph with real edge lengths and with no negative cycles, we show how to compute single-source shortest path distances in the graph in O(n(log n)^2/loglog n) time with O(n) space. This is an improvement of a recent time bound of O(n(log n)^2) by Klein et al.

M3 - Working paper

BT - Korteste Veje i Planare Grafer med Reelle Kantvægte i O(n(log n)^2/loglog n) Tid

CY - Datalogisk Institut, Københavns Universitet (DIKU)

ER -