<p>This PhD thesis, consisting of an introduction, four papers, and some supplementary results, studies the problem of finding an <i>optimal realization</i> 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.</p><p>It has been conjectured that <i>extremally weighted</i> optimal realizations may be found as subgraphs of the <i>hereditarily optimal realization</i> Γ<sub>d</sub>, 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 <i>tight span</i> of the metric.</p><p>In Paper I, we prove that the graph Γ<sub>d</sub> is equivalent to the 1-skeleton of the tight span precisely when the metric considered is <i>totally split-decomposable</i>. For the subset of totally split-decomposable metrics known as <i>consistent</i> metrics this implies that Γ<sub>d</sub> is isomorphic to the easily constructed <i>Buneman graph</i>.</p><p>In Paper II, we show that for any metric on at most five points, any optimal realization can be found as a subgraph of Γ<sub>d</sub>.</p><p>In Paper III we provide a series of counterexamples; metrics for which there exist extremally weighted optimal realizations which are not subgraphs of Γ<sub>d</sub>. However, for these examples there also exists at least one optimal realization which is a subgraph.</p><p>Finally, Paper IV examines a weakened conjecture suggested by the above counterexamples: can we always find some optimal realization as a subgraph in Γ<sub>d</sub>? Defining <i>extremal</i> 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 Γ<sub>d</sub> is injective. Moreover, we prove that this weakened conjecture holds for the subset of consistent metrics which have a 2-dimensional tight span</p>
| Identifer | oai:union.ndltd.org:UPSALLA/oai:DiVA.org:uu-8297 |
| Date | January 2007 |
| Creators | Lesser, Alice |
| Publisher | Uppsala University, Department of Mathematics, Uppsala : Matematiska institutionen |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Doctoral thesis, comprehensive summary, text |
| Relation | Uppsala Dissertations in Mathematics, 1401-2049 ; 52 |
Page generated in 0.0021 seconds