Jump to content
Change search PrimeFaces.cw("Fieldset","widget_formSmash_search",{id:"formSmash:search",widgetVar:"widget_formSmash_search",toggleable:true,collapsed:true,toggleSpeed:500,behaviors:{toggle:function(ext) {PrimeFaces.ab({s:"formSmash:search",e:"toggle",f:"formSmash",p:"formSmash:search"},ext);}}});
$(function(){PrimeFaces.cw("Dialog","citationDialog",{id:"formSmash:upper:j_idt195",widgetVar:"citationDialog",width:"800",height:"600"});});
$(function(){PrimeFaces.cw("ImageSwitch","widget_formSmash_j_idt981",{id:"formSmash:j_idt981",widgetVar:"widget_formSmash_j_idt981",fx:"fade",speed:500,timeout:8000},"imageswitch");});
#### Open Access in DiVA

####

#### Search in DiVA

##### By author/editor

Lesser, Alice
##### By organisation

Department of Mathematics
#### Search outside of DiVA

GoogleGoogle Scholar$(function(){PrimeFaces.cw('Chart','widget_formSmash_j_idt1176_0_downloads',{id:'formSmash:j_idt1176:0:downloads',type:'bar',responsive:true,data:[[7,6,1,4,8,4,8,9,11,3]],title:"Downloads of File (FULLTEXT01)",axes:{xaxis: {label:"",renderer:$.jqplot.CategoryAxisRenderer,tickOptions:{angle:-90}},yaxis: {label:"",min:0,max:20,renderer:$.jqplot.LinearAxisRenderer,tickOptions:{angle:0}}},series:[{label:'diva2:170958'}],ticks:["Dec -23","Jan -24","Feb -24","Mar -24","Apr -24","May -24","Jun -24","Jul -24","Aug -24","Oct -24"],orientation:"vertical",barMargin:3,datatip:true,datatipFormat:"<span style=\"display:none;\">%2$d</span><span>%2$d</span>"},'charts');}); Total: 746 downloads$(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_j_idt1179",{id:"formSmash:j_idt1179",widgetVar:"widget_formSmash_j_idt1179",target:"formSmash:downloadLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade"});}); findCitings = function() {PrimeFaces.ab({s:"formSmash:j_idt1181",f:"formSmash",u:"formSmash:citings",pa:arguments[0]});};$(function() {findCitings();}); $(function(){PrimeFaces.cw('Chart','widget_formSmash_visits',{id:'formSmash:visits',type:'bar',responsive:true,data:[[45,212,299,183,286,179,124,124,77,6]],title:"Visits for this publication",axes:{xaxis: {label:"",renderer:$.jqplot.CategoryAxisRenderer,tickOptions:{angle:-90}},yaxis: {label:"",min:0,max:310,renderer:$.jqplot.LinearAxisRenderer,tickOptions:{angle:0}}},series:[{label:'diva2:170958'}],ticks:["Feb -24","Mar -24","Apr -24","May -24","Jun -24","Jul -24","Aug -24","Sep -24","Oct -24","Nov -24"],orientation:"vertical",barMargin:3,datatip:true,datatipFormat:"<span style=\"display:none;\">%2$d</span><span>%2$d</span>"},'charts');}); Total: 4451 hits
$(function(){PrimeFaces.cw("Dialog","citationDialog",{id:"formSmash:lower:j_idt1275",widgetVar:"citationDialog",width:"800",height:"600"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt175",{id:"formSmash:upper:j_idt175",widgetVar:"widget_formSmash_upper_j_idt175",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt176_j_idt178",{id:"formSmash:upper:j_idt176:j_idt178",widgetVar:"widget_formSmash_upper_j_idt176_j_idt178",target:"formSmash:upper:j_idt176: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_idt470",{id:"formSmash:j_idt470",widgetVar:"widget_formSmash_j_idt470",multiple:true});
##### Supervisors

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt482",{id:"formSmash:j_idt482",widgetVar:"widget_formSmash_j_idt482",multiple:true}); Available from: 2007-11-07 Created: 2007-11-07 Last updated: 2022-01-28Bibliographically 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_idt532:0:j_idt537",widgetVar:"overlay170953",target:"formSmash:j_idt532: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_idt532:1:j_idt537",widgetVar:"overlay170954",target:"formSmash:j_idt532: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_idt532:2:j_idt537",widgetVar:"overlay170955",target:"formSmash:j_idt532: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_idt532:3:j_idt537",widgetVar:"overlay170956",target:"formSmash:j_idt532:3:partsLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

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

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

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