English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problems of maintaining an approximate maximum matching andan approximate minimum vertex cover in a dynamic graph undergoing a sequence ofedge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld[STOC 2010], this problem has received significant attention in recent years.Very recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011],Solomon [FOCS 2016] gave a randomized dynamic algorithm for this problem thathas an approximation ratio of $2$ and an amortised update time of $O(1)$ withhigh probability. This algorithm requires the assumption of an {\em obliviousadversary}, meaning that the future sequence of edge insertions/deletions inthe graph cannot depend in any way on the algorithm's past output. A naturalway to remove the assumption on oblivious adversary is to give a deterministicdynamic algorithm for the same problem in $O(1)$ update time. In this paper, weresolve this question.  We present a new {\em deterministic} fully dynamic algorithm that maintains a$O(1)$-approximate minimum vertex cover and maximum fractional matching, withan amortised update time of $O(1)$. Previously, the best deterministicalgorithm for this problem was due to Bhattacharya, Henzinger and Italiano[SODA 2015]; it had an approximation ratio of $(2+\epsilon)$ and an amortisedupdate time of $O(\log n/\epsilon^2)$. Our results also extend to a fullydynamic $O(f^3)$-approximate algorithm with $O(f^2)$ amortized update time forthe hypergraph vertex cover and fractional hypergraph matching problems, whereevery hyperedge has at most $f$ vertices.

Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in $O(1)$ Amortized Update Time