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

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n vertex graphs using a trivial deterministic"algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the naive 0(n) one was reported up to this date. The only progress in this direction is due to Ivkovie and Lloyd, who in 1993 devised a deterministic algorithm with an amortized update time of 0((n + m)boolean AND 5/2), where m is the number of edges. In this article, we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic worst-case update time of O(m). Moreover, our algorithm maintains a matching, which in fact is a 3/2-approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2 - epsilon)-approximate MCM improving upon the naive 0(n) was known prior to this work, even allowing amortized time bounds and randomization. For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with sublogarithmic update time. Specifically, it maintains a fully dynamic maximal matching with amortized update time of 0(logn/ log log n). This result addresses an open question of Onak and Rubinfeld [2010]. We also show a deterministic algorithm with optimal space usage, which for arbitrary graphs maintains a maximal matching in amortized O(m) time and uses only O(n + m) space.

Simple Deterministic Algorithms for Fully Dynamic Maximal Matching