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

Computing a maximum independent set (MaxIS) is a fundamental NP-hard problemin graph theory, which has important applications in a wide spectrum of fields.Since graphs in many applications are changing frequently over time, theproblem of maintaining a MaxIS over dynamic graphs has attracted increasingattention over the past few years. Due to the intractability of maintaining anexact MaxIS, this paper aims to develop efficient algorithms that can maintainan approximate MaxIS with an accuracy guarantee theoretically. In particular,we propose a framework that maintains a $(\frac{\Delta}{2} + 1)$-approximateMaxIS over dynamic graphs and prove that it achieves a constant approximationratio in many real-world networks. To the best of our knowledge, this is thefirst non-trivial approximability result for the dynamic MaxIS problem.Following the framework, we implement an efficient linear-time dynamicalgorithm and a more effective dynamic algorithm with near-linear expected timecomplexity. Our thorough experiments over real and synthetic graphs demonstratethe effectiveness and efficiency of the proposed algorithms, especially whenthe graph is highly dynamic.

Dynamic Approximate Maximum Independent Set on Massive Graphs