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.