A unified framework for hopsets

DOI10.4230/LIPICS.ESA.2022.81MaRDI QIDQ6969597zbMATH OpenFDO

Authors Ofer Neiman, Idan Shabat

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.81

zbMATH Keywords

graph algorithmshopsetsshortest paths

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• A Randomized Parallel Algorithm for Single-Source Shortest Paths
• Approximate distance oracles
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Distributed distance computation and routing with small messages
• Exponentially Faster Shortest Paths in the Congested Clique
• Fast Approximate Shortest Paths in the Congested Clique
• Hopsets with constant hopbound, and applications to approximate shortest paths
• New (α, β) Spanners and Hopsets
• On efficient distributed construction of near optimal routing schemes
• Parallel approximate undirected shortest paths via low hop emulators
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Ramanujan graphs
• Spanners and emulators with sublinear distance errors
• Thorup-Zwick emulators are universally optimal hopsets

Cited in

(2)

• On the size overhead of pairwise spanners
• Lightweight near-additive spanners

This page was built for publication: A unified framework for hopsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969597)