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_idt219",widgetVar:"citationDialog",width:"800",height:"600"});});
$(function(){PrimeFaces.cw("ImageSwitch","widget_formSmash_j_idt1279",{id:"formSmash:j_idt1279",widgetVar:"widget_formSmash_j_idt1279",fx:"fade",speed:500,timeout:8000},"imageswitch");});
#### Open Access in DiVA

No full text in DiVA
#### Other links

Publisher's full textScopus
#### Authority records

Persson, Mia
#### Search in DiVA

##### By author/editor

Persson, Mia
##### By organisation

Department of Computer Science and Media Technology (DVMT)
On the subject

Mathematics
#### Search outside of DiVA

GoogleGoogle ScholarfindCitings = function() {PrimeFaces.ab({s:"formSmash:j_idt1679",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:[[3,5,2,2,2,4,2,7,3,3]],title:"Visits for this publication",axes:{yaxis: {label:"",min:0,max:10,renderer:$.jqplot.LinearAxisRenderer,tickOptions:{angle:0}},xaxis: {label:"",renderer:$.jqplot.CategoryAxisRenderer,tickOptions:{angle:-90}}},series:[{label:'diva2:1685506'}],ticks:["Oct -23","Nov -23","Dec -23","Feb -24","Mar -24","Apr -24","May -24","Jun -24","Jul -24","Aug -24"],orientation:"vertical",barMargin:3,datatip:true,datatipFormat:"<span style=\"display:none;\">%2$d</span><span>%2$d</span>"},'charts');}); Total: 70 hits
$(function(){PrimeFaces.cw("Dialog","citationDialog",{id:"formSmash:lower:j_idt1818",widgetVar:"citationDialog",width:"800",height:"600"});});

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

An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic GraphsPrimeFaces.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();
}
}
2022 (English)In: CALDAM 2022: Algorithms and Discrete Applied Mathematic, Springer, 2022, p. 140-151Conference paper, Published paper (Refereed)
##### Abstract [en]

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

Springer, 2022. p. 140-151
##### Series

Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349 ; 13179
##### Keywords [en]

Directed graphs, Forestry, Graphic methods, Trees (mathematics), All pairs shortest paths, Directed paths, Integer parameters, Output-sensitive algorithm, Parameter T, Positive integers, Real edge weights, Shortest path problem, Single source shortest path problems, Weighted directed graph, Parameter estimation
##### National Category

Mathematics
##### Identifiers

URN: urn:nbn:se:mau:diva-54295DOI: 10.1007/978-3-030-95018-7_12Scopus ID: 2-s2.0-85124662790ISBN: 978-3-030-95017-0 (print)ISBN: 978-3-030-95018-7 (electronic)OAI: oai:DiVA.org:mau-54295DiVA, id: diva2:1685506
##### Conference

Conference on Algorithms and Discrete Applied Mathematics 2022
#####

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt589",{id:"formSmash:j_idt589",widgetVar:"widget_formSmash_j_idt589",multiple:true}); Available from: 2022-08-03 Created: 2022-08-03 Last updated: 2024-06-17Bibliographically approved

First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. Given a positive integer parameter t, in O(tm) time the algorithm finds for each vertex v a path distance from the source to v not exceeding that yielded by the shortest path from the source to v among the so called t+ light paths. A directed path between two vertices is t+ light if it contains at most t more edges than the minimum edge-cardinality directed path between these vertices. For t= O(n), our algorithm yields an O(nm)-time solution to SSSP in directed graphs with real edge weights matching that of Bellman and Ford. Our main contribution is a new, output-sensitive algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input graph. If the trees are sufficiently thin on the average, the algorithm is substantially faster than the best known algorithm. Finally, we discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles. © 2022, Springer Nature Switzerland AG.

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

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