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 consider the problem of finding maximum flows in planar graphs withcapacities on both vertices and edges and with multiple sources and sinks. Wepresent three algorithms when the capacities are integers. The first algorithmruns in $O(n \log^3 n + kn)$ time when all capacities are bounded, where $n$ isthe number of vertices in the graph and $k$ is the number of terminals. Thisalgorithm is the first to solve the vertex-disjoint paths problem innear-linear time when $k$ is bounded but larger than 2. The second algorithmruns in $O(k^2(k^3 + \Delta) n \text{ polylog} (nU))$ time, where $U$ is thelargest finite capacity of a single vertex and $\Delta$ is the maximum degreeof a vertex. Finally, when $k=3$, we present an algorithm that runs in $O(n\log n)$ time; this algorithm works even when the capacities are arbitraryreals. Our algorithms improve on the fastest previously known algorithms when$k$ and $\Delta$ are small and $U$ is bounded by a polynomial in $n$. Prior tothis result, the fastest algorithms ran in $O(n^2 / \log n)$ time for realcapacities and $O(n^{3/2} \log n \log U)$ for integer capacities.

Maximum Integer Flows in Directed Planar Graphs with Multiple Sources and Sinks and Vertex Capacities