We consider the point-to-point (approximate) shortest-path query problem, which is the
following generalization of the classical single-source (SSSP) and all-pairs shortest-path …

This survey provides a guiding reference to researchers seeking an overview of the large
body of literature about graph spanners. It surveys the current literature covering various …

Let G=(V, E) be an undirected weighted graph with| V|= n and| E|= m. Let k≥ 1 be an
integer. We show that G=(V, E) can be preprocessed in O (kmn 1/k) expected time …

The “short cycle removal” technique was recently introduced by Abboud, Bringmann, Khoury
and Zamir (STOC'22) to prove fine-grained hardness of approximation. Its main technical …

Although there are many advanced and specialized texts and handbooks on algorithms,
until now there was no book that focused exclusively on the wide variety of data structures …

We present a new technique for efficiently removing almost all short cycles in a graph
without unintentionally removing its triangles. Consequently, triangle finding problems do …

Abstract Let G=(V, E) be an undirected weighted graph on| V|= n vertices and| E|= m edges.
A t‐spanner of the graph G, for any t≥ 1, is a subgraph (V, ES), ES⊆ E, such that the …

Thorup and Zwick showed that for any integer k≥ 1, it is possible to preprocess any
positively weighted undirected graph G=(V, E), with| E|= m and| V|= n, in Õ (kmn ^\rm1/\itk) …

Among the most important graph parameters is the Diameter, the largest distance between
any two vertices. There are no known very efficient algorithms for computing the Diameter …

The paper concerns graph spanners that are resistant to vertex or edge failures. Given a
weighted undirected n-vertex graph G=(V, E) and an integer k≥ 1, the subgraph H=(V, E') …