Parametric Shortest Paths in a Linearly Interpolated Graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910118399967232 |
|---|---|
| author | Sriraman, Jacob Barton, Eli Fasy, Brittany Terese Millman, David L. Mumey, Brendan Rengo, Nate Sopp, Braeden Tumuluri, Vasishta Zhu, Binhai |
| author_facet | Sriraman, Jacob Barton, Eli Fasy, Brittany Terese Millman, David L. Mumey, Brendan Rengo, Nate Sopp, Braeden Tumuluri, Vasishta Zhu, Binhai |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_08892 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Parametric Shortest Paths in a Linearly Interpolated Graph Sriraman, Jacob Barton, Eli Fasy, Brittany Terese Millman, David L. Mumey, Brendan Rengo, Nate Sopp, Braeden Tumuluri, Vasishta Zhu, Binhai Computational Geometry 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. |
| title | Parametric Shortest Paths in a Linearly Interpolated Graph |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2604.08892 |