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

Sensitive Distance and Reachability Oracles for Large Batch UpdatesPrimeFaces.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();
}
}
2019 (English)In: 2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019), IEEE COMPUTER SOC , 2019, p. 424-435Conference paper, Published paper (Refereed)
##### Abstract [en]

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

IEEE COMPUTER SOC , 2019. p. 424-435
##### Series

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

sensitive oracle, emergency oracle, failure, batch, reachability, distance
##### National Category

Computer and Information Sciences
##### Identifiers

URN: urn:nbn:se:kth:diva-269513DOI: 10.1109/FOCS.2019.00034ISI: 000510015300025Scopus ID: 2-s2.0-85078436479ISBN: 978-1-7281-4952-3 (print)OAI: oai:DiVA.org:kth-269513DiVA, id: diva2:1412841
##### Conference

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), NOV 09-12, 2019, Baltimore, MD
#####

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

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

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

In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph G with n nodes and integer weights from [-W, W]. Second, given a single batch of f edge insertions and deletions, we update the data structure. Third, given a query pair of nodes (u, v), return the distance from u to v. In the easier problem called sensitive reachability oracle problem, we only ask if there exists a directed path from u to v. Our first result is a sensitive distance oracle with (O) over tilde (W n(omega+(3-omega)mu)) preprocessing time, (O) over tilde (Wn(2-mu) f(2) + Wnf(omega)) update time, and (O) over tilde (Wn(2-mu) f + Wnf(2)) query time where the parameter mu is an element of [0, 1] can be chosen. The data-structure requires O(Wn(2+mu) log n) bits of memory. This is the first algorithm that can handle f >= log n updates. Previous results (e.g. [Demetrescu et al. SICOMP'08; Bernstein and Karger SODA'08 and FOCS'09; Duan and Pettie SODA'09; Grandoni and Williams FOCS'121) can handle at most 2 updates. When 3 <= f <= log n, the only non-trivial algorithm was by [Weimann and Yuster FOCS'10]. When W = (O) over tilde (1), our algorithm simultaneously improves their preprocessing time, update time, and query time. In particular, when f = omega(1), their update and query time is Omega(n(2-o(1))), while our update and query time are truly subquadratic in n, i.e., ours is faster by a polynomial factor of n. To highlight the technique, ours is the first graph algorithm that exploits the kernel basis decomposition of polynomial matrices by [Jeannerod and Villard J.Comp'05; Zhou, Labahn and Storjohann J.Comp'151 developed in the symbolic computation community. As an easy observation from our technique, we obtain the first sensitive reachability oracle can handle f >= log n updates. Our algorithm has O(n(omega)) preprocessing time, O(f(omega)) update time, and O(f(2)) query time. This data-structure requires O(n(2) log n) bits of memory. Efficient sensitive reachability oracles were asked in [Chechik, Cohen, Fiat, and Kaplan SODA'17]. Our algorithm can handle any constant number of updates in constant time. Previous algorithms with constant update and query time can handle only at most f <= 2 updates. Otherwise, there are non-trivial results for f <= log n, though, with query time Omega(n) by adapting [Baswana, Choudhary and Roditty STOC'16].

QC 20200309

Available from: 2020-03-09 Created: 2020-03-09 Last updated: 2020-03-09Bibliographically approved
doi
isbn
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1519",{id:"formSmash:j_idt1519",widgetVar:"widget_formSmash_j_idt1519",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

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