Parametric Shortest Paths in a Linearly Interpolated Graph
This addresses a specific algorithmic problem in graph theory, likely incremental as it builds on parametric shortest path concepts.
The paper tackles the problem of computing all distinct parametric shortest paths in a linearly interpolated graph, achieving a data structure with construction time of Θ(k|E|log|V|) and query time of Θ(log k), where k is the number of distinct paths.
We consider the parametric shortest paths problem in a linearly interpolated graph. Given two positively-weighted directed graphs $G_0=(V,E,Ï_0)$ and $G_1=(V,E,Ï_1),$ the linearly interpolated graph is the family of graphs $(1-λ)G_0+λG_1$, parameterized by $λ\in [0,1]$. The problem is to compute all distinct parametric shortest paths. We compute a data structure in $Î(k|E|\log |V|)$ time, where~$k$ is the number of distinct parametric shortest paths over all~$λ\in [0,1]$ that exist for a nontrivial interval of parameters, each corresponding to a linear function in a maximal sub-interval of $[0,1]$. Using this data structure, a shortest path query takes~$Î(\log k)$ time.