A lecture on Diameter and center computations in
large graphs from practical issues to theoretical aspects
by Michel Habib
(NoNA Spring School on Algorithms,
Istanbul, 12-15 March, 2009)
Abstract
Starting from an application on networks and a surprisingly
good linear time heuristic computing exact diameter on very
large graphs, we try to explain this efficiency using our
knowledge on graph classes and graph parameters. We also
survey in this context recent results using delta-hyperbolic
metric spaces as defined by Gromov.