Sökning: id:"swepub:oai:DiVA.org:uu-270646" >
Optimal realization...
-
Herrmann, SvenUniv E Anglia, Sch Comp Sci, Norwich NR4 7TJ, Norfolk, England.
(författare)
Optimal realizations of two-dimensional, totally-decomposable metrics
- Artikel/kapitelEngelska2015
Förlag, utgivningsår, omfång ...
-
Elsevier BV,2015
-
printrdacarrier
Nummerbeteckningar
-
LIBRIS-ID:oai:DiVA.org:uu-270646
-
https://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-270646URI
-
https://doi.org/10.1016/j.disc.2015.02.008DOI
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:art swepub-publicationtype
Anmärkningar
-
A realization of a metric d on a finite set X is a weighted graph (G, w) whose vertex set contains X such that the shortest-path distance between elements of X considered as vertices in G is equal to d. Such a realization (G, w) is called optimal if the sum of its edge weights is minimal over all such realizations. Optimal realizations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. A. Dress (1984) showed that the optimal realizations of a metric dare closely related to a certain polytopal complex that can be canonically associated to d called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of d must always contain an optimal realization as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally-decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realizations of two-dimensional totally-decomposable metrics. (C) 2015 Elsevier B.V. All rights reserved.
Ämnesord och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Koolen, Jack H.Univ Sci & Technol China, Sch Math Sci, Wen Tsun Wu Key Lab, CAS, Hefei, Peoples R China.
(författare)
-
Lesser, AliceUppsala universitet,Matematiska institutionen(Swepub:uu)alles844
(författare)
-
Moulton, VincentUniv E Anglia, Sch Comp Sci, Norwich NR4 7TJ, Norfolk, England.
(författare)
-
Wu, TaoyangUniv E Anglia, Sch Comp Sci, Norwich NR4 7TJ, Norfolk, England.;Natl Univ Singapore, Dept Math, Singapore 119076, Singapore.
(författare)
-
Univ E Anglia, Sch Comp Sci, Norwich NR4 7TJ, Norfolk, England.Univ Sci & Technol China, Sch Math Sci, Wen Tsun Wu Key Lab, CAS, Hefei, Peoples R China.
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i:Discrete Mathematics: Elsevier BV338:8, s. 1289-12990012-365X1872-681X
Internetlänk
Hitta via bibliotek
Till lärosätets databas