Shortest Paths in Planar Graphs with Real Lengths in $O(n{\log }^{2}n/\log \log n)$ 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{\log }^{2}n/\log \log n)$ time with O(n) space. This is an improvement of a recent time bound of $O(n{\log }^{2}n)$ by Klein et al.

Cited by in corpus (1)

• Multiple-source multiple-sink maximum flow in planar graphs