Median Networks

Median networks, alias median graphs, have been rediscovered many times (in different mathematical languages). It is thus clear that they form a useful tool in many areas and are interesting on their own.

In the first part of the talk (given by S. Klavzar) we will recall some classical results on median graphs, like the fact that they are precisely the retracts of hypercubes. Then we will follow with some more recent results, for instance the so-called Euler-type formulas and the concept of cube polynomials (and its relation to median graphs).

In the second part (by W. Imrich) the focus will be on algorithms for the recognition of median graphs and related classes of graphs. Conceptually simple and easy to implement algorithms, more efficient but still practical ones and algorithms of purely theoretical interest will be treated. The talk ends with a list of open problems.