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

Distributed Exact Weighted All-Pairs Shortest Paths in (O)over-tilde(n(5/4)) RoundsPrimeFaces.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();
}
}
2017 (English)In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2017, p. 168-179Conference paper, Published paper (Refereed)
##### Abstract [en]

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

IEEE, 2017. p. 168-179
##### Series

Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
##### Keywords [en]

distributed graph algorithms, all-pairs shortest paths, exact distributed algorithms
##### National Category

Electrical Engineering, Electronic Engineering, Information Engineering
##### Identifiers

URN: urn:nbn:se:kth:diva-220659DOI: 10.1109/FOCS.2017.24ISI: 000417425300015Scopus ID: 2-s2.0-85041116469ISBN: 978-1-5386-3464-6 (print)OAI: oai:DiVA.org:kth-220659DiVA, id: diva2:1172111
##### Conference

58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), OCT 15-17, 2017, Berkeley, CA
#####

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt488",{id:"formSmash:j_idt488",widgetVar:"widget_formSmash_j_idt488",multiple:true});
##### Funder

EU, Horizon 2020, 715672Swedish Research Council, 2015-04659
##### Note

##### In thesis

We study computing all-pairs shortest paths (APSP) on distributed networks (the CONGEST model). The goal is for every node in the (weighted) network to know the distance from every other node using communication. The problem admits (1+ o(1))-approximation (O) over tilde (n)-time algorithms [2], [3], which are matched with (Omega) over tilde (n)-time lower bounds [3], [4], [5](1). No omega(n) lower bound or o(m) upper bound were known for exact computation. In this paper, we present an (O) over tilde (n(5/4))-time randomized (Las Vegas) algorithm for exact weighted APSP; this provides the first improvement over the naive O(m)-time algorithm when the network is not so sparse. Our result also holds for the case where edge weights are asymmetric (a. k. a. the directed case where communication is bidirectional). Our techniques also yield an (O) over tilde (n(3/4) k(1/2) + n)-time algorithm for the k-source shortest paths problem where we want every node to know distances from k sources; this improves Elkin's recent bound [6] when k = (omega) over tilde (n(1/4)). We achieve the above results by developing distributed algorithms on top of the classic scaling technique, which we believe is used for the first time for distributed shortest paths computation. One new algorithm which might be of an independent interest is for the reversed r-sink shortest paths problem, where we want every of r sinks to know its distances from all other nodes, given that every node already knows its distance to every sink. We show an (O) over tilde (n root r)-time algorithm for this problem. Another new algorithm is called short range extension, where we show that in (O) over tilde (n root h) time the knowledge about distances can be "extended" for additional h hops. For this, we use weight rounding to introduce small additive errors which can be later fixed. Remark: Independently from our result, Elkin recently observed in [6] that the same techniques from an earlier version of the same paper (https://arxiv.org/abs/1703.01939v1) led to an O(n(5/3) log(2/3) n)-time algorithm.

QC 20170109

Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-07-24Bibliographically approved1. Dynamic algorithms: new worst-case and instance-optimal bounds via new connections$(function(){PrimeFaces.cw("OverlayPanel","overlay1234277",{id:"formSmash:j_idt828:0:j_idt832",widgetVar:"overlay1234277",target:"formSmash:j_idt828:0:parentLink",showEvent:"mousedown",hideEvent:"mousedown",showEffect:"blind",hideEffect:"fade",appendToBody:true});});

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

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