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

We give the first almost-linear time algorithms for several problems inincremental graphs including cycle detection, strongly connected componentmaintenance, $s$-$t$ shortest path, maximum flow, and minimum-cost flow. Tosolve these problems, we give a deterministic data structure that returns a$m^{o(1)}$-approximate minimum-ratio cycle in fully dynamic graphs in amortized$m^{o(1)}$ time per update. Combining this with the interior point methodframework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear timealgorithm for deciding the first update in an incremental graph after which thecost of the minimum-cost flow attains value at most some given threshold $F$.By rather direct reductions to minimum-cost flow, we are then able to solve theproblems in incremental graphs mentioned above.  At a high level, our algorithm dynamizes the $\ell_1$ oblivious routing ofRozho\v{n}-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method toextract an approximate minimum ratio cycle from the structure of the obliviousrouting. To maintain the oblivious routing, we use tools from concurrent workof Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers forshortest paths, in order to maintain a sparse neighborhood cover in fullydynamic graphs.  To find a cycle, we first show that an approximate minimum ratio cycle can berepresented as a fundamental cycle on a small set of trees resulting from theoblivious routing. Then, we find a cycle whose quality is comparable to thebest tree cycle. This final cycle query step involves vertex and edgesparsification procedures reminiscent of previous works, but crucially requiresa more powerful dynamic spanner which can handle far more edge insertions. Webuild such a spanner via a construction that hearkens back to the classicgreedy spanner algorithm.

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, $s$-$t$ Shortest Path, and Minimum-Cost Flow