Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
Liam Roditty, Ariel Sapir · 2026
Read Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs by Liam Roditty, Ariel Sapir (2026) 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-2604-26831.txt.
Introduction
Roditty and Sapir introduce a generalized family of emulators for weighted graphs. It extends the +2W1 spanner and +4W1 emulator of Elkin, Gitlitz and Neiman. Their stretch parameters depend on k, with separate even and odd cases built from the heaviest and second-heaviest edges, W1 and W2, on a shortest path. The framework improves stretch over state-of-the-art emulators and spanners for unweighted graphs in a specific distance regime. It beats the Thorup-Zwick additive emulator for vertex pairs within a stated distance bound.
Catalog record
| CREATOR | Liam Roditty, Ariel Sapir |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 1198637 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26831