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/

Zendy Plus

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

Zendy Tools

Zendy Open

We study reachability and shortest paths problems in dynamic directed graphs.Whereas algebraic dynamic data structures supporting edge updates andreachability/distance queries have been known for quite a long time, they donot, in general, allow reporting the underlying paths within the same timebounds, especially against an adaptive adversary.  In this paper we develop the first known fully dynamic reachability datastructures working against an adaptive adversary and supporting edge updatesand path queries for two natural variants: (1) point-to-point path reporting,and (2) single-source reachability tree reporting. For point-to-point queriesin DAGs, we achieve $O(n^{1.529})$ worst-case update and query bounds, whereasfor tree reporting in DAGs, the worst-case bounds are $O(n^{1.765})$. Moreimportantly, we show how to lift these algorithms to work on general graphs atthe cost of increasing the bounds to $n^{1+5/6+o(1)}$ and making the updatetimes amortized. On the way to accomplishing that, we obtain two interestingsubresults. We give subquadratic fully dynamic algorithms for topological order(in a DAG), and strongly connected components. To the best of our knowledge,such algorithms have not been described before.  Additionally, we provide deterministic incremental data structures forreachability and shortest paths that handle edge insertions and report therespective paths within subquadratic worst-case time bounds. For reachabilityand $(1+\epsilon)$-approximate shortest paths in weighted digraphs, thesebounds match the best known dynamic matrix inverse-based randomized bounds forfully dynamic reachability [v.d.Brand, Nanongkai and Saranurak, FOCS'19]. Forexact shortest paths in unweighted graphs, the obtained bounds in theincremental setting polynomially improve upon the respective best knownrandomized update/distance query bounds in the fully dynamic setting.

Subquadratic Dynamic Path Reporting in Directed Graphs Against an Adaptive Adversary