An introduction to median graphs and event structures via the computation of the eccentricities

29th of April 2022, at 09:30 (morning)

Room: Online via Teams

https://teams.microsoft.com/l/meetup-join/19%3adacd63e97f9e48e896f537ace22a27bf%40thread.tacv2/1650923909103?context=%7b%22Tid%22%3a%2281e7c4de-26c9-4531-b076-b70e2d75966e%22%2c%22Oid%22%3a%22c00d08df-c86f-4f81-a9c8-6287a3bb947d%22%7d

Speaker: Pierre Bergé

Title: An introduction to median graphs and event structures via the computation of the eccentricities

Abstract:

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 stand as important objects in geometric group theory. Furthermore, median graphs 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 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. Then, we present some open questions related to this topic, in particular dealing with the correspondence between median graphs and event structures.