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

Conditional lower bounds for dynamic graph problems has received a great dealof attention in recent years. While many results are now known for thefully-dynamic case and such bounds often imply worst-case bounds for thepartially dynamic setting, it seems much more difficult to prove amortizedbounds for incremental and decremental algorithms. In this paper we considerpartially dynamic versions of three classic problems in graph theory. Based onpopular conjectures we show that:  -- No algorithm with amortized update time $O(n^{1-\varepsilon})$ exists forincremental or decremental maximum cardinality bipartite matching. Thissignificantly improves on the $O(m^{1/2-\varepsilon})$ bound for sparse graphsof Henzinger et al. [STOC'15] and $O(n^{1/3-\varepsilon})$ bound of Kopelowitz,Pettie and Porat. Our linear bound also appears more natural. In addition, theresult we present separates the node-addition model from the edge insertionmodel, as an algorithm with total update time $O(m\sqrt{n})$ exists for theformer by Bosek et al. [FOCS'14].  -- No algorithm with amortized update time $O(m^{1-\varepsilon})$ exists forincremental or decremental maximum flow in directed and weighted sparse graphs.No such lower bound was known for partially dynamic maximum flow previously.Furthermore no algorithm with amortized update time $O(n^{1-\varepsilon})$exists for directed and unweighted graphs or undirected and weighted graphs.  -- No algorithm with amortized update time $O(n^{1/2 - \varepsilon})$ existsfor incremental or decremental $(4/3-\varepsilon')$-approximating the diameterof an unweighted graph. We also show a slightly stronger bound if nodeadditions are allowed. [...]

On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter