Hopsets and spanners are fundamental graph structures, playing a key role in shortest path
computation, distributed communication, and more. A (near-exact) hopset for a given graph …

This paper introduces stronger notions for approximate single-source shortest-path
distances and gives simple reductions to compute them from weaker standard notions of …

For an n-vertex digraph G=(V, E) and integer parameter D, a D-shortcut is a small set H of
directed edges taken from the transitive closure of G, satisfying that the diameter of G∪ H is …

For a graph G, a D-diameter-reducing exact hopset is a small set of additional edges H that,
when added to G, maintains its graph metric but guarantees that all node pairs have a …

A classic 1993 paper by Althöfer et al. proved a tight reduction from spanners, emulators,
and distance oracles to the extremal function γ of high-girth graphs. This paper initiated a …

We study the well-known shortcut set problem: how much can one decrease the diameter of
a directed graph by adding a small set of shortcuts from the transitive closure of the graph …

For an n-vertex m-edge digraph G, a D-shortcut is a small set H of directed edges taken from
the transitive closure of G, satisfying that the diameter of G∪ H is at most D. In a sequence of …

The hereditary discrepancy of a set system is a certain quantitative measure of the
pseudorandom properties of the system. Roughly, hereditary discrepancy measures how …

Spanners for metric spaces have been extensively studied, perhaps most notably in low-
dimensional Euclidean spaces-due to their numerous applications. Euclidean spanners can …

For an n-vertex directed graph G=(V, E), a β-shortcut set H is a set of additional edges H⊆
V× V such that GUH has the same transitive closure as G, and for every pair u, v∈ V, there is …