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

Let $G = (V,E,w)$ be a weighted, digraph subject to a sequence of adversarialedge deletions. In the decremental single-source reachability problem (SSR), weare given a fixed source $s$ and the goal is to maintain a data structure thatcan answer path-queries $s \rightarrowtail v$ for any $v \in V$. In the moregeneral single-source shortest paths (SSSP) problem the goal is to return anapproximate shortest path to $v$, and in the SCC problem the goal is tomaintain strongly connected components of $G$ and to answer path queries withineach component. All of these problems have been very actively studied over thepast two decades, but all the fast algorithms are randomized and, moresignificantly, they can only answer path queries if they assume a weaker model:they assume an oblivious adversary which is not adaptive and must fix theupdate sequence in advance. This assumption significantly limits the use ofthese data structures, most notably preventing them from being used assubroutines in static algorithms. All the above problems are notoriouslydifficult in the adaptive setting. In fact, the state-of-the-art is still theEven and Shiloach tree, which dates back all the way to 1981 and achieves totalupdate time $O(mn)$. We present the first algorithms to break through thisbarrier:  1) deterministic decremental SSR/SCC with total update time $mn^{2/3 + o(1)}$  2) deterministic decremental SSSP with total update time $n^{2+2/3+o(1)}$.  To achieve these results, we develop two general techniques of broaderinterest for working with dynamic graphs: 1) a generalization of expander-basedtools to dynamic directed graphs, and 2) a technique that we call congestionbalancing and which provides a new method for maintaining flow underadversarial deletions. Using the second technique, we provide the firstnear-optimal algorithm for decremental bipartite matching.

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing