uu.seUppsala University Publications

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

Optimal and Hereditarily Optimal Realizations of Metric SpacesPrimeFaces.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});
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();
}
}
2007 (English)Doctoral thesis, comprehensive summary (Other academic)Alternative title
##### Abstract [en]

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

Uppsala: Matematiska institutionen , 2007. , p. 70
##### Series

Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 52
##### Keywords [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
##### Keywords [sv]

Tillämpad matematik
##### Identifiers

URN: urn:nbn:se:uu:diva-8297ISBN: 978-91-506-1967-6 (print)OAI: oai:DiVA.org:uu-8297DiVA, id: diva2:170958
##### Public defence

2007-11-30, Polhemssalen, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 10:15
##### Opponent

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt460",{id:"formSmash:j_idt460",widgetVar:"widget_formSmash_j_idt460",multiple:true});
##### Supervisors

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt472",{id:"formSmash:j_idt472",widgetVar:"widget_formSmash_j_idt472",multiple:true}); Available from: 2007-11-07 Created: 2007-11-07Bibliographically approved
##### List of papers

Optimala och ärftligt optimala realiseringar av metriker (Swedish)

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

1. Hereditarily optimal realizations of consistent metrics$(function(){PrimeFaces.cw("OverlayPanel","overlay170953",{id:"formSmash:j_idt539:0:j_idt545",widgetVar:"overlay170953",target:"formSmash:j_idt539:0:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

2. Optimal realizations of generic 5-point metrics$(function(){PrimeFaces.cw("OverlayPanel","overlay170954",{id:"formSmash:j_idt539:1:j_idt545",widgetVar:"overlay170954",target:"formSmash:j_idt539:1:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

3. Optimal and h-optimal realizations for 5-point metrics: appendix to "Optimal realizations of generic 5-point metrics"$(function(){PrimeFaces.cw("OverlayPanel","overlay170955",{id:"formSmash:j_idt539:2:j_idt545",widgetVar:"overlay170955",target:"formSmash:j_idt539:2:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

4. Concerning the relationship between realizations and tight spans of finite metrics$(function(){PrimeFaces.cw("OverlayPanel","overlay170956",{id:"formSmash:j_idt539:3:j_idt545",widgetVar:"overlay170956",target:"formSmash:j_idt539:3:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

5. Extremal Optimal Realizations$(function(){PrimeFaces.cw("OverlayPanel","overlay170957",{id:"formSmash:j_idt539:4:j_idt545",widgetVar:"overlay170957",target:"formSmash:j_idt539:4:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

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

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