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

CREATORYael Kirkpatrick, Virginia Vassilevska Williams
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE151 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-22261

Browse the full library · About the Tower of Babel