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

We study the maximum $s,t$-flow oracle problem on planar directed graphswhere the goal is to design a data structure answering max $s,t$-flow value (orequivalently, min $s,t$-cut value) queries for arbitrary source-target pairs$(s,t)$. For the case of polynomially bounded integer edge capacities, wedescribe an exact max $s,t$-flow oracle with truly subquadratic space andpreprocessing, and sublinear query time. Moreover, if$(1-\epsilon)$-approximate answers are acceptable, we obtain a static oraclewith near-linear preprocessing and $\tilde{O}(n^{3/4})$ query time and adynamic oracle supporting edge capacity updates and queries in$\tilde{O}(n^{6/7})$ worst-case time.  To the best of our knowledge, for directed planar graphs, no (approximate)max $s,t$-flow oracles have been described even in the unweighted case, andonly trivial tradeoffs involving either no preprocessing or precomputing allthe $n^2$ possible answers have been known.  One key technical tool we develop on the way is a sublinear (in the number ofedges) algorithm for finding a negative cycle in so-called dense distancegraphs. By plugging it in earlier frameworks, we obtain improved bounds forother fundamental problems on planar digraphs. In particular, we show: (1) adeterministic $O(n\log(nC))$ time algorithm for negatively-weighted SSSP inplanar digraphs with integer edge weights at least $-C$. This improves upon thepreviously known bounds in the important case of weights polynomial in $n$, and(2) an improved $O(n\log{n})$ bound on finding a perfect matching in abipartite planar graph.

Max $s,t$-Flow Oracles and Negative Cycle Detection in Planar Digraphs