Shortest Paths in Multimode Graphs
Yael Kirkpatrick, Virginia Vassilevska Williams · 2025
Read Shortest Paths in Multimode Graphs by Yael Kirkpatrick, Virginia Vassilevska Williams (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-22261.txt.
Description
Yael Kirkpatrick and Virginia Vassilevska Williams study shortest paths when a traveler must pick one network and stick to it, in a 2025 paper. A multimode graph layers several networks on the same points, like rival airlines, and the distance between two points is the best single-mode distance. Mixing modes mid-trip is not allowed.
For two modes on undirected graphs, they give a fast three-approximation for the diameter, then sharpen it to factors of two and two and a half. Radius gets a three-approximation for any number of modes. Directed graphs get a test for whether routes exist at all, and lower bounds show several of these results are tight.
Catalog record
| CREATOR | Yael Kirkpatrick, Virginia Vassilevska Williams |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 151 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-22261