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

CREATORLiam Roditty, Ariel Sapir
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE1198637
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.26831

Browse the full library · About the Tower of Babel