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
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:uu-8297 |
| Date | January 2007 |
| Creators | Lesser, Alice |
| Publisher | Uppsala universitet, Matematiska institutionen, Uppsala : Matematiska institutionen |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | English |
| Type | Doctoral thesis, comprehensive summary, info:eu-repo/semantics/doctoralThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | Uppsala Dissertations in Mathematics, 1401-2049 ; 52 |
Page generated in 0.0026 seconds