In this article, we show how to compute for n-vertex planar graphs in O (n 11/6 polylog (n))
expected time the diameter and the sum of the pairwise distances. The algorithms work for …

In this paper, we propose to use the concept of local fairness for auditing and ranking
redistricting plans. Given a redistricting plan, a deviating group is a population-balanced …

We present an O (n 1.5)-space distance oracle for directed planar graphs that answers
distance queries in O (log n) time. Our oracle both significantly simplifies and significantly …

For a set of graphs\({\mathcal {H}}\), a graph G is\({\mathcal {H}}\)-subgraph-free if G does
not contain any graph from\({{{\mathcal {H}}}}\) as a subgraph. We propose general and easy …

We present new algorithmic results for the class of Helly graphs, that is, for the discrete
analogues of hyperconvex metric spaces. Specifically, an undirected unweighted graph is …

We develop a new approach for distributed distance computation in planar graphs that is
based on a variant of the metric compression problem recently introduced by Abboud et …

Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs
cannot be computed in truly subquadratic time. Nevertheless there are several graph …

Abstract $\newcommand {\OO}[1]{O\left (# 1\right)}\newcommand {\eps}{\varepsilon} $ We
present the first near-linear-time algorithm that computes a $(1+\eps) $-approximation of the …

Under the strong exponential-time hypothesis, the diameter of general unweighted graphs
cannot be computed in truly subquadratic time (in the size of the input), as shown by Roditty …

We consider the problem of preprocessing a weighted directed planar graph in order to
quickly answer exact distance queries. The main tension in this problem is between space S …