The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

PLG

Seminar

Optimal and hereditarily optimal realisation of metric spaces

Lesser, A (Uppsala)
Friday 07 September 2007, 10:20-10:40

Seminar Room 1, Newton Institute

Abstract

Given a finite set X and a metric d on X, a realization of (X,d) is a weighted graph G=(V,E,w) such that X is a subset of V and the distance d(x,y) between any pair of elements in X is the shortest distance between x and y in G. A realization such that the total edge weight of G is minimal is known as an optimal realization. It is well-known that if there exists a tree which is a realization of (X,d) then this tree is the unique optimal realization. In general however, optimal realizations are not trees, not necessarily unique, and notoriously hard to find. It has been suggested by Andreas Dress that optimal realizations may be possible to find by deleting edges in a larger graph known as the hereditarily optimal realization of the given metric, which is unique and can be explicitly calculated. Both optimal and hereditarily optimal realizations can be useful concepts in phylogenetics, especially when studying e.g. plants or viruses, where a phylogenetic tree is not necessarily the best representation of the evolutionary relationships.

We will outline some recent progress on this problem, showing both that optimal realizations can be found within hereditarily optimal realizations for all metrics on less than five elements, but also that there exist counterexamples, which in turn give rise to new questions.

Related Links

Presentation

[pdf ] [ps  ]

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧