uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Optimal and Hereditarily Optimal Realizations of Metric Spaces
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Matematiska institutionen.
2007 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)Alternativ tittel
Optimala och ärftligt optimala realiseringar av metriker (svensk)
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

sted, utgiver, år, opplag, sider
Uppsala: Matematiska institutionen , 2007. , s. 70
Serie
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 52
Emneord [en]
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
Emneord [sv]
Tillämpad matematik
Identifikatorer
URN: urn:nbn:se:uu:diva-8297ISBN: 978-91-506-1967-6 (tryckt)OAI: oai:DiVA.org:uu-8297DiVA, id: diva2:170958
Disputas
2007-11-30, Polhemssalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 10:15
Opponent
Veileder
Tilgjengelig fra: 2007-11-07 Laget: 2007-11-07bibliografisk kontrollert
Delarbeid
1. Hereditarily optimal realizations of consistent metrics
Åpne denne publikasjonen i ny fane eller vindu >>Hereditarily optimal realizations of consistent metrics
2006 Inngår i: Annals of Combinatorics, ISSN 02180006, Vol. 10, nr 1, s. 63-76Artikkel i tidsskrift (Fagfellevurdert) Published
Identifikatorer
urn:nbn:se:uu:diva-96393 (URN)
Tilgjengelig fra: 2007-11-07 Laget: 2007-11-07bibliografisk kontrollert
2. Optimal realizations of generic 5-point metrics
Åpne denne publikasjonen i ny fane eller vindu >>Optimal realizations of generic 5-point metrics
2009 (engelsk)Inngår i: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 30, nr 5, s. 1164-1171Artikkel i tidsskrift (Fagfellevurdert) 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.

HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-96394 (URN)10.1016/j.ejc.2008.09.021 (DOI)000265517800014 ()
Tilgjengelig fra: 2007-11-07 Laget: 2007-11-07 Sist oppdatert: 2017-12-14bibliografisk kontrollert
3. Optimal and h-optimal realizations for 5-point metrics: appendix to "Optimal realizations of generic 5-point metrics"
Åpne denne publikasjonen i ny fane eller vindu >>Optimal and h-optimal realizations for 5-point metrics: appendix to "Optimal realizations of generic 5-point metrics"
Manuskript (Annet vitenskapelig)
Identifikatorer
urn:nbn:se:uu:diva-96395 (URN)
Tilgjengelig fra: 2007-11-07 Laget: 2007-11-07 Sist oppdatert: 2010-01-13bibliografisk kontrollert
4. Concerning the relationship between realizations and tight spans of finite metrics
Åpne denne publikasjonen i ny fane eller vindu >>Concerning the relationship between realizations and tight spans of finite metrics
2007 (engelsk)Inngår i: Discrete & Computational Geometry, ISSN 0179-5376, E-ISSN 1432-0444, Vol. 38, nr 3, s. 605-614Artikkel i tidsskrift (Fagfellevurdert) Published
Abstract [en]

Given a metric d on a finite set X, a realization of d is a weighted graph $G=(V,E,w\colon \ E \to {\Bbb R}_{>0})$ with $X \subseteq V$ such that for all $x,y \in X$ the length of any shortest path in G between x and y equals d(x,y). In this paper we consider two special kinds of realizations, optimal realizations and hereditarily optimal realizations, and their relationship with the so-called tight span. In particular, we present an infinite family of metrics {dk}k≥1, and—using a new characterization for when the so-called underlying graph of a metric is an optimal realization that we also present—we prove that dk has (as a function of k) exponentially many optimal realizations with distinct degree sequences. We then show that this family of metrics provides counter-examples to a conjecture made by Dress in 1984 concerning the relationship between optimal realizations and the tight span, and a negative reply to a question posed by Althofer in 1988 on the relationship between optimal and hereditarily optimal realizations.

HSV kategori
Identifikatorer
urn:nbn:se:uu:diva-96396 (URN)10.1007/s00454-007-1352-5 (DOI)000249696700007 ()
Tilgjengelig fra: 2007-11-07 Laget: 2007-11-07 Sist oppdatert: 2017-12-14bibliografisk kontrollert
5. Extremal Optimal Realizations
Åpne denne publikasjonen i ny fane eller vindu >>Extremal Optimal Realizations
Manuskript (Annet vitenskapelig)
Identifikatorer
urn:nbn:se:uu:diva-96397 (URN)
Tilgjengelig fra: 2007-11-07 Laget: 2007-11-07 Sist oppdatert: 2010-01-13bibliografisk kontrollert

Open Access i DiVA

fulltekst(620 kB)572 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 620 kBChecksum SHA-1
911b3f8be0bbaf4eb60a31d10d19465648956e0f8849204268c4df2132e4e4e7b9728ab6
Type fulltextMimetype application/pdf
omslag(38 kB)33 nedlastinger
Filinformasjon
Fil COVER01.pdfFilstørrelse 38 kBChecksum SHA-1
45f8ce7b17d206b13288f6155a4614258db9ad8f49ab1e30a369ccc4ec6292f8532b7943
Type coverMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 572 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

isbn
urn-nbn

Altmetric

isbn
urn-nbn
Totalt: 1940 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf