uu.seUppsala University Publications

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt159",{id:"formSmash:upper:j_idt159",widgetVar:"widget_formSmash_upper_j_idt159",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt160_j_idt163",{id:"formSmash:upper:j_idt160:j_idt163",widgetVar:"widget_formSmash_upper_j_idt160_j_idt163",target:"formSmash:upper:j_idt160:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Optimal realizations of two-dimensional, totally-decomposable metricsPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true}); PrimeFaces.cw("SelectBooleanButton","widget_formSmash_j_idt238",{id:"formSmash:j_idt238",widgetVar:"widget_formSmash_j_idt238",onLabel:"Hide others and affiliations",offLabel:"Show others and affiliations"});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2015 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 338, no 8, p. 1289-1299Article in journal (Refereed) Published
##### Resource type

Text
##### Abstract [en]

##### Place, publisher, year, edition, pages

2015. Vol. 338, no 8, p. 1289-1299
##### Keyword [en]

Optimal realizations, Totally-decomposable metrics, Tight-span, Manhattan network problem, Buneman complex
##### National Category

Discrete Mathematics
##### Identifiers

URN: urn:nbn:se:uu:diva-270646DOI: 10.1016/j.disc.2015.02.008ISI: 000365146100003OAI: oai:DiVA.org:uu-270646DiVA, id: diva2:890210
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt456",{id:"formSmash:j_idt456",widgetVar:"widget_formSmash_j_idt456",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt462",{id:"formSmash:j_idt462",widgetVar:"widget_formSmash_j_idt462",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt468",{id:"formSmash:j_idt468",widgetVar:"widget_formSmash_j_idt468",multiple:true});
Available from: 2016-01-01 Created: 2016-01-01 Last updated: 2017-12-01Bibliographically approved

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.

doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1452",{id:"formSmash:j_idt1452",widgetVar:"widget_formSmash_j_idt1452",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1505",{id:"formSmash:lower:j_idt1505",widgetVar:"widget_formSmash_lower_j_idt1505",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1506_j_idt1508",{id:"formSmash:lower:j_idt1506:j_idt1508",widgetVar:"widget_formSmash_lower_j_idt1506_j_idt1508",target:"formSmash:lower:j_idt1506:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});