Median graphs and median related structures admit many characterizations and nice properties. The cube complexes of median graphs are exactly the CAT(0) cube complexes, which represent one of the most studied object in geometric group theory. Furthermore, median graphs also arise in concurrency theory and phylogenetics. We study the computation of metric parameters on this family of graphs: median set, diameter, eccentricities and reach centralities. In particular, in a very recent result, it is shown that all eccentricities can be computed in subquadratic-time on median graphs. We introduce the algorithmic techniques employed to tackle median graphs and present some open questions related to this topic.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne