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

A minimum cycle basis of a weighted undirected graph $G$ is a basis of thecycle space of $G$ such that the total weight of the cycles in this basis isminimized. If $G$ is a planar graph with non-negative edge weights, such abasis can be found in $O(n^2)$ time and space, where $n$ is the size of $G$. Weshow that this is optimal if an explicit representation of the basis isrequired. We then present an $O(n^{3/2}\log n)$ time and $O(n^{3/2})$ spacealgorithm that computes a minimum cycle basis \emph{implicitly}. From thisresult, we obtain an output-sensitive algorithm that explicitly computes aminimum cycle basis in $O(n^{3/2}\log n + C)$ time and $O(n^{3/2} + C)$ space,where $C$ is the total size (number of edges and vertices) of the cycles in thebasis. These bounds reduce to $O(n^{3/2}\log n)$ and $O(n^{3/2})$,respectively, when $G$ is unweighted. We get similar results for the all-pairsmin cut problem since it is dual equivalent to the minimum cycle basis problemfor planar graphs. We also obtain $O(n^{3/2}\log n)$ time and $O(n^{3/2})$space algorithms for finding, respectively, the weight vector and a Gomory-Hutree of $G$. The previous best time and space bound for these two problems wasquadratic. From our Gomory-Hu tree algorithm, we obtain the following result:with $O(n^{3/2}\log n)$ time and $O(n^{3/2})$ space for preprocessing, theweight of a min cut between any two given vertices of $G$ can be reported inconstant time. Previously, such an oracle required quadratic time and space forpreprocessing. The oracle can also be extended to report the actual cut in timeproportional to its size.

Minimum Cycle Basis and All-Pairs Min Cut of a Planar Graph in Subquadratic Time