{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih7cy5remmkwq7a6ra2iuta2dlaku5lfuqg4iqshurikgatbnwihq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjebckk5f7t2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.08892v1",
  "publishedAt": "2026-04-13T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Jacob Sriraman",
    "Eli Barton",
    "Brittany Terese Fasy",
    "David L. Millman",
    "Brendan Mumey",
    "Nate Rengo",
    "Braeden Sopp",
    "Vasishta Tumuluri",
    "Binhai Zhu"
  ],
  "textContent": "**Authors:** Jacob Sriraman, Eli Barton, Brittany Terese Fasy, David L. Millman, Brendan Mumey, Nate Rengo, Braeden Sopp, Vasishta Tumuluri, Binhai Zhu\n\nWe 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"
}