Shortest paths in planar graphs with real lengths in O(nlog2n/loglogn) time

Shay Mozes; Christian Wulff-Nilsen

doi:10.1007/978-3-642-15781-3_18

Shortest paths in planar graphs with real lengths in O(nlog²n/loglogn) time

Shay Mozes, Christian Wulff-Nilsen

Datalogisk Institut

40 Citationer (Scopus)

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/log log n) time with O(n) space. This improves on a recent O(n log² n) time bound by Klein et al.

Originalsprog	Engelsk
Titel	Algorithms – ESA 2010 : 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II
Redaktører	Mark de Berg, Ulrich Meyer
Antal sider	12
Vol/bind	Part II
Forlag	Springer
Publikationsdato	2010
Sider	206-217
ISBN (Trykt)	978-3-642-15780-6
ISBN (Elektronisk)	978-3-642-15781-3
DOI	https://doi.org/10.1007/978-3-642-15781-3_18
Status	Udgivet - 2010
Begivenhed	18th Annual European Symposium on Algorithms - Liverpool, Storbritannien Varighed: 6 sep. 2010 → 8 sep. 2010 Konferencens nummer: 18

Konference

Konference	18th Annual European Symposium on Algorithms
Nummer	18
Land/Område	Storbritannien
By	Liverpool
Periode	06/09/2010 → 08/09/2010

Adgang til dokumentet

10.1007/978-3-642-15781-3_18

http://arxiv.org/pdf/0911.4963v1

Citationsformater

Shortest paths in planar graphs with real lengths in O(nlog²n/loglogn) time. / Mozes, Shay; Wulff-Nilsen, Christian.
Algorithms – ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II. red. / Mark de Berg; Ulrich Meyer. Bind Part II Springer, 2010. s. 206-217.

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Mozes, S & Wulff-Nilsen, C 2010, Shortest paths in planar graphs with real lengths in O(nlog²n/loglogn) time. i M de Berg & U Meyer (red), Algorithms – ESA 2010: 18th Annual European Symposium, Liverpool, UK, September 6-8, 2010. Proceedings, Part II. bind Part II, Springer, s. 206-217, 18th Annual European Symposium on Algorithms, Liverpool, Storbritannien, 06/09/2010. https://doi.org/10.1007/978-3-642-15781-3_18

@inproceedings{37e390e023ce11df8ed1000ea68e967b,

title = "Shortest paths in planar graphs with real lengths in O(nlog2n/loglogn) time",

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 log2 n/log log n) time with O(n) space. This improves on a recent O(n log2 n) time bound by Klein et al.",

author = "Shay Mozes and Christian Wulff-Nilsen",

year = "2010",

doi = "10.1007/978-3-642-15781-3_18",

language = "English",

isbn = "978-3-642-15780-6",

volume = "Part II",

pages = "206--217",

editor = "{de Berg}, Mark and Ulrich Meyer",

booktitle = "Algorithms – ESA 2010",

publisher = "Springer",

note = "18th Annual European Symposium on Algorithms ; Conference date: 06-09-2010 Through 08-09-2010",

}

TY - GEN

T1 - Shortest paths in planar graphs with real lengths in O(nlog2n/loglogn) time

AU - Mozes, Shay

AU - Wulff-Nilsen, Christian

N1 - Conference code: 18

PY - 2010

Y1 - 2010

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 log2 n/log log n) time with O(n) space. This improves on a recent O(n log2 n) time bound 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 log2 n/log log n) time with O(n) space. This improves on a recent O(n log2 n) time bound by Klein et al.

U2 - 10.1007/978-3-642-15781-3_18

DO - 10.1007/978-3-642-15781-3_18

M3 - Article in proceedings

SN - 978-3-642-15780-6

VL - Part II

SP - 206

EP - 217

BT - Algorithms – ESA 2010

A2 - de Berg, Mark

A2 - Meyer, Ulrich

PB - Springer

T2 - 18th Annual European Symposium on Algorithms

Y2 - 6 September 2010 through 8 September 2010