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});});

Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log(3) n) Worst Case 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();
}
}
2017 (English)In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery (ACM), 2017, p. 470-489Conference paper, Published paper (Refereed)
##### Abstract [en]

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

Association for Computing Machinery (ACM), 2017. p. 470-489
##### Series

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
##### National Category

Computer Sciences
##### Identifiers

URN: urn:nbn:se:kth:diva-243622ISI: 000426965800030Scopus ID: 2-s2.0-85016184685ISBN: 9781611974782 (print)OAI: oai:DiVA.org:kth-243622DiVA, id: diva2:1287106
##### Conference

28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Hotel Porta Fira, Barcelona, Spain, 16 January 2017 through 19 January 2017
#####

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});
##### Funder

EU, FP7, Seventh Framework Programme, FP/2007-2013EU, European Research Council, 340506
##### Note

We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + epsilon) and worst case update time O(m(1/4)/epsilon(2)) where m is the number of edges in the graph. In recent past, Gupta and Peng [FOGS 2013] gave a deterministic data structure with approximation ratio (1 + epsilon) and worst case update time O(root mT/epsilon(2)). No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised update time O(log(2) n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOGS 2011] and Solomon [FOGS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O(1). We bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + epsilon) and worst case update time O(log(3) n), for all sufficiently small constants epsilon.

QC 20190208

Available from: 2019-02-08 Created: 2019-02-08 Last updated: 2019-08-20Bibliographically approved
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});});