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 …

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 …

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 …

Spanners, emulators, and approximate distance oracles can be viewed as lossy
compression schemes that represent an unweighted graph metric in small space, say …

We survey problems, results, ideas, and recent progress in the Ribe program. The goal of
this research program, which is motivated by a classical rigidity theorem of Martin Ribe, is to …

Shortest distance queries are essential not only in graph analysis and graph mining tasks
but also in database applications, when a large graph needs to be dealt with. Such shortest …

In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann [9]
showed that exact distance queries on planar graphs could be answered in no (1) time by a …

We present new and improved data structures that answer exact node-to-node distance
queries in planar graphs. Such data structures are also known as distance oracles. For any …

We give the first improvement to the space/approximation trade-off of distance oracles since
the seminal result of Thorup and Zwick. For unweighted undirected graphs, our distance …

We give the first improvement to the space/approximation trade-off of distance oracles since
the seminal result of Thorup and Zwick [STOC'01]. For unweighted graphs, our distance …