uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Optimal realizations of generic 5-point metrics
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics. Uppsala University, Disciplinary Domain of Science and Technology, Biology, Department of Cell and Molecular Biology, The Linnaeus Centre for Bioinformatics.
2009 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 30, no 5, 1164-1171 p.Article in journal (Refereed) Published
Abstract [en]

Given a metric cl oil a finite set X, a realization of d is a triple (G, phi, omega) consisting of a graph G = (V, E), a labeling phi : X -> V, and a weighting omega : E -> R->0 such that for all x, y is an element of X the length of any shortest path in G between phi(x) and phi(y) equals d(x, y). Such a realization is called optimal if parallel to G parallel to := Sigma(e is an element of E) omega(e) is minimal amongst all realizations of d. In this paper we will consider optimal realizations of generic five-point metric spaces. In particular, we show that there is a canonical subdivision C Of the metric fail of five-point metrics into cones such that (i) every metric d in the interior of a cone C is an element of C has a unique optimal realization (G, phi, omega), (ii) if d' is also in the interior of C with optimal realization (G', phi', omega') then (G, phi) and (G',  phi') are isomorphic as labeled graphs, and (iii) any labeled graph that underlies all optimal realizations of the metrics in the interior of some cone C e C must belong to one of three isomorphism classes.

Place, publisher, year, edition, pages
2009. Vol. 30, no 5, 1164-1171 p.
National Category
URN: urn:nbn:se:uu:diva-96394DOI: 10.1016/j.ejc.2008.09.021ISI: 000265517800014OAI: oai:DiVA.org:uu-96394DiVA: diva2:170954
Available from: 2007-11-07 Created: 2007-11-07 Last updated: 2010-07-30Bibliographically approved
In thesis
1. Optimal and Hereditarily Optimal Realizations of Metric Spaces
Open this publication in new window or tab >>Optimal and Hereditarily Optimal Realizations of Metric Spaces
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
Alternative title[sv]
Optimala och ärftligt optimala realiseringar av metriker
Abstract [en]

This PhD thesis, consisting of an introduction, four papers, and some supplementary results, studies the problem of finding an optimal realization of a given finite metric space: a weighted graph which preserves the metric's distances and has minimal total edge weight. This problem is known to be NP-hard, and solutions are not necessarily unique.

It has been conjectured that extremally weighted optimal realizations may be found as subgraphs of the hereditarily optimal realization Γd, a graph which in general has a higher total edge weight than the optimal realization but has the advantages of being unique, and possible to construct explicitly via the tight span of the metric.

In Paper I, we prove that the graph Γd is equivalent to the 1-skeleton of the tight span precisely when the metric considered is totally split-decomposable. For the subset of totally split-decomposable metrics known as consistent metrics this implies that Γd is isomorphic to the easily constructed Buneman graph.

In Paper II, we show that for any metric on at most five points, any optimal realization can be found as a subgraph of Γd.

In Paper III we provide a series of counterexamples; metrics for which there exist extremally weighted optimal realizations which are not subgraphs of Γd. However, for these examples there also exists at least one optimal realization which is a subgraph.

Finally, Paper IV examines a weakened conjecture suggested by the above counterexamples: can we always find some optimal realization as a subgraph in Γd? Defining extremal optimal realizations as those having the maximum possible number of shortest paths, we prove that any embedding of the vertices of an extremal optimal realization into Γd is injective. Moreover, we prove that this weakened conjecture holds for the subset of consistent metrics which have a 2-dimensional tight span

Place, publisher, year, edition, pages
Uppsala: Matematiska institutionen, 2007. 70 p.
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 52
Applied mathematics, optimal realization, hereditarily optimal realization, tight span, phylogenetic network, Buneman graph, split decomposition, T-theory, finite metric space, topological graph theory, discrete geometry, Tillämpad matematik
urn:nbn:se:uu:diva-8297 (URN)978-91-506-1967-6 (ISBN)
Public defence
2007-11-30, Polhemssalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 10:15
Available from: 2007-11-07 Created: 2007-11-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Department of MathematicsThe Linnaeus Centre for Bioinformatics
In the same journal
European journal of combinatorics (Print)

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 161 hits
ReferencesLink to record
Permanent link

Direct link