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

Research output: Working paperResearch

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.
Translated title of the contributionShortest Paths in Planar Graphs with Real Lengths in O(n(log n)^2/loglog n) Time
Original languageEnglish
Place of PublicationDatalogisk Institut, Københavns Universitet (DIKU)
Number of pages15
Publication statusPublished - 2009

ID: 12874166