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

Christian Wulff-Nilsen

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

Bidragets oversatte titel: Shortest Paths in Planar Graphs with Real Lengths in O(n(log n)^2/loglog n) Time

Datalogisk Institut

Abstract

Givet en planar orienteret graf med n knuder, med reelle kantvægte og med ingen kredse af negativ vægt, viser vi, hvordan afstanden fra en given knude til alle andre knuder i grafen kan bestemmes i O(n(log n)^2/loglog n) tid med O(n) plads. Dette er en forbedring af en O(n(log n)^2)-tids-algoritme af Klein et al.

Bidragets oversatte titel	Shortest Paths in Planar Graphs with Real Lengths in O(n(log n)^2/loglog n) Time
Originalsprog	Engelsk
Udgivelsessted	Datalogisk Institut, Københavns Universitet (DIKU)
Antal sider	15
Status	Udgivet - 2009

Citationsformater

@techreport{0732552065a211de8bc9000ea68e967b,

title = "Korteste Veje i Planare Grafer med Reelle Kantv{\ae}gte i O(n(log n)^2/loglog n) Tid",

abstract = "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.",

author = "Christian Wulff-Nilsen",

year = "2009",

language = "English",

type = "WorkingPaper",

}

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 -

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

Abstract

Fingeraftryk

Citationsformater