A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs
Preprint
Abstract
Given an $n$-vertex planar embedded digraph $G$ with non-negative edge weights and a face $f$ of $G$, Klein presented a data structure with $O(n\log n)$ space and preprocessing time which can answer any query $(u,v)$ for the shortest path distance in $G$ from $u$ to $v$ or from $v$ to $u$ in $O(\log n)$ time, provided $u$ is on $f$. This data structure is a key tool in a number of state-of-the-art algorithms and data structures for planar graphs. Klein's data structure relies on dynamic trees and the persistence technique as well as a highly non-trivial interaction between primal shortest path trees and their duals. The construction of our data structure follows a completely different and in our opinion very simple divide-and-conquer approach that solely relies on Single-Source Shortest Path computations and contractions in the primal graph. Our space and preprocessing time bound is $O(n\log |f|)$ and query time is $O(\log |f|)$ which is an improvement over Klein's data structure when $f$ has small size.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Faster shortest paths in dense distance graphs, with applicationsTheoretical Computer Science, 2018
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear TimeSIAM Journal on Computing, 2017
- Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing TimeACM Transactions on Algorithms, 2015
- Multiple-Source Shortest Paths in Embedded GraphsSIAM Journal on Computing, 2013
- Dynamic trees in practiceACM Journal of Experimental Algorithmics, 2009
- Planar graphs, negative weight edges, shortest paths, and near linear timeJournal of Computer and System Sciences, 2006
- Compact oracles for reachability and approximate distances in planar digraphsJournal of the ACM, 2004
- Faster Shortest-Path Algorithms for Planar GraphsJournal of Computer and System Sciences, 1997
- Making data structures persistentJournal of Computer and System Sciences, 1989