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

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update TimePrimeFaces.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();
}
}
2018 (English)In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 65, no 6, article id 36Article in journal (Refereed) Published
##### Abstract [en]

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

Association for Computing Machinery (ACM), 2018. Vol. 65, no 6, article id 36
##### Keywords [en]

Approximate shortest paths, hop sets
##### National Category

Computational Mathematics
##### Identifiers

URN: urn:nbn:se:kth:diva-240781DOI: 10.1145/3218657ISI: 000452840200002Scopus ID: 2-s2.0-85057196421OAI: oai:DiVA.org:kth-240781DiVA, id: diva2:1275928
#####

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt1130",{id:"formSmash:j_idt1130",widgetVar:"widget_formSmash_j_idt1130",multiple:true});
##### Note

In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1 + is an element of)-approximation factor, the running time was recently improved to n(2)(+o(1)) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1 + is an element of)-approximation algorithm with m(1+)(o(1)) expected total update time, thus obtaining near-linear time. Moreover, we obtain m(1)(+)(o(1)) log W time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn) time is the mn(0.9+o(1))-time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (h, is an element of)-hop set introduced by Cohen [12] in the PRAM literature. An (h, is an element of)-hop set of a graph G = (V, E) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1 + is an element of)-approximated by their h-hop distance (given by a path containing at most h edges) on G' = (V, E boolean OR F). Our algorithm can maintain an (n(o(1)), is an element of)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Madry [27]. These two new tools might be of independent interest.

QC 20190107

Available from: 2019-01-07 Created: 2019-01-07 Last updated: 2019-01-07Bibliographically approved
doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1840",{id:"formSmash:j_idt1840",widgetVar:"widget_formSmash_j_idt1840",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

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