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

Pierre Bergé, Guillaume Ducoffe, Michel Habib

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 cla…