# Faster Shortest Paths in Dense Distance Graphs, with Applications

Preprint · Shay Mozes, Yahav Nussbaum, Oren Weimann

- Archive id: arxiv:1404.0977
- Published: 2014-04-03
- arXiv: https://arxiv.org/abs/1404.0977
- Citations: 2
- Source URL: https://arxiv.org/abs/1404.0977
- PDF: https://arxiv.org/pdf/1404.0977
- Provenance: arxiv

## Abstract

We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao \[STOC'94\]. The second is Fakcharoenphol and Rao's algorithm \[FOCS'01\] for emulating Dijkstra's algorithm on the dense distance graph (DDG). A DDG is defined for a decomposition of a planar graph $G$ into regions of at most $r$ vertices each, for some parameter $r \< n$. The vertex set of the DDG is the set of $Θ(n/\\sqrt r)$ vertices of $G$ that belong to more than one region (boundary vertices). The DDG has $Θ(n)$ arcs, such that distances in the DDG are equal to the distances in $G$. Fakcharoenphol and Rao's implementation of Dijkstra's algorithm on the DDG (nicknamed FR-Dijkstra) runs in $O(n\\log(n) r^{-1/2} \\log r)$ time, and is a key component in many state-of-the-art planar graph algorithms for shortest paths, minimum cuts, and maximum flows. By combining these two techniques we remove the $\\log n$ dependency in the running time of the shortest-path algorithm, making it $O(n r^{-1/2} \\log^2r)$. This work is part of a research agenda that aims to develop new techniques that would lead to faster, possibly linear-time, algorithms for problems such as minimum-cut, maximum-flow, and shortest paths with negative arc lengths. As immediate applications, we show how to compute maximum flow in directed weighted planar graphs in $O(n \\log p)$ time, where $p$ is the minimum number of edges on any path from the source to the sink. We also show how to compute any part of the DDG that corresponds to a region with $r$ vertices and $k$ boundary vertices in $O(r \\log k)$ time, which is faster than has been previously known for small values of $k$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.