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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The first fully dynamic algorithm for maintaining a maximal independent set(MIS) with update time that is sublinear in the number of edges was presentedrecently by the authors of this paper [Assadi et.al. STOC'18]. The algorithm isdeterministic and its update time is $O(m^{3/4})$, where $m$ is the(dynamically changing) number of edges. Subsequently, Gupta and Khan andindependently Du and Zhang [arXiv, April 2018] presented deterministicalgorithms for dynamic MIS with update times of $O(m^{2/3})$ and $O(m^{2/3}\sqrt{\log m})$, respectively. Du and Zhang also gave a randomized algorithmwith update time $\widetilde{O}(\sqrt{m})$. Moreover, they provided somepartial (conditional) hardness results hinting that update time of$m^{1/2-\epsilon}$, and in particular $n^{1-\epsilon}$ for $n$-vertex densegraphs, is a natural barrier for this problem for any constant $\epsilon >0$,for both deterministic and randomized algorithms that satisfy a certain naturalproperty.  In this paper, we break this natural barrier and present the first fullydynamic (randomized) algorithm for maintaining an MIS with update time that isalways sublinear in the number of vertices, namely, an$\widetilde{O}(\sqrt{n})$ expected amortized update time algorithm. We alsoshow that a simpler variant of our algorithm can already achieve an$\widetilde{O}(m^{1/3})$ expected amortized update time, which results in animproved performance over our $\widetilde{O}(\sqrt{n})$ update time algorithmfor sufficiently sparse graphs, and breaks the $m^{1/2}$ barrier of Du andZhang for all values of $m$.

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time