
























We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion or insertion updates to the graph, our parallel algorithm adjusts the maximal matching to these updates in $poly(\log n)$ depth and using $poly(\log n)$ amortized work per update. That is, the amortized work for processing a batch of $k$ updates is $kpoly(\log n)$, while all this work is done in $poly(\log n)$ depth, with high probability. This can be seen as a parallel counterpart of the sequential dynamic algorithms for constant-approximate and maximal matching [Onak and Rubinfeld STOC'10; Baswana, Gupta, and Sen FOCS'11; and Solomon FOCS'16]. Our algorithm readily generalizes to maximal matching in hypergraphs of rank $r$ -- where each hyperedge has at most $r$ endpoints -- with a $poly(r)$ increase in work, while retaining the $poly(\log n)$ depth.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。