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

In this paper we study minimum cut and maximum flow problems on planargraphs, both in static and in dynamic settings. First, we present an algorithmthat given an undirected planar graph computes the minimum cut between any twogiven vertices in O(n log log n) time. Second, we show how to achieve the sameO(n log log n) bound for the problem of computing maximum flows in undirectedplanar graphs. To the best of our knowledge, these are the first algorithms forthose two problems that break the O(n log n) barrier, which has been standingfor more than 25 years. Third, we present a fully dynamic algorithm that isable to maintain information about minimum cuts and maximum flows in a planegraph (i.e., a planar graph with a fixed embedding): our algorithm is able toinsert edges, delete edges and answer min-cut and max-flow queries between anypair of vertices in O(n^(2/3) log^3 n) time per operation. This result is basedon a new dynamic shortest path algorithm for planar graphs which may be ofindependent interest. We remark that this is the first known non-trivialalgorithm for min-cut and max-flow problems in a dynamic setting.

Improved Minimum Cuts and Maximum Flows in Undirected Planar Graphs