Quasilinear-time eccentricities computation, and more, on median graphs

Abstract

Computing the diameter, and more generally, all eccentricities of an undirected graph is an important problem in algorithmic graph theory and the challenge is to identify graph classes for which their computation can be achieved in subquadratic time. Using a new recursive scheme based on the structural properties of median graphs, we provide a quasilinear-time algorithm to determine all eccentricities for this well-known family of graphs. The gist of our technique is to identify the balanced and unbalanced parts of the Θ-class decomposition of median graphs, which are then processed using different recursive schemes. The exact running time of our algorithm is in O (n log4 n ). This outcome not only answers a question asked by Bénéteau et al. (2020) but also greatly improves the recent combinatorial algorithm of Berge et al. (2022) for the same problem, running in time O (n1.6408 logO (1) n ).

Authors

* External Author