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

Let $G$ be an edge-weighted directed graph with $n$ vertices embedded on anorientable surface of genus $g$. We describe a simple deterministiclexicographic perturbation scheme that guarantees uniqueness of minimum-costflows and shortest paths in $G$. The perturbations take $O(gn)$ time tocompute. We use our perturbation scheme in a black box manner to derive adeterministic $O(n \log \log n)$ time algorithm for minimum cut in\emph{directed} edge-weighted planar graphs and a deterministic $O(g^2 n \logn)$ time proprocessing scheme for the multiple-source shortest paths problem ofcomputing a shortest path oracle for all vertices lying on a common face of asurface embedded graph. The latter result yields faster deterministicnear-linear time algorithms for a variety of problems in constant genus surfaceembedded graphs.  Finally, we open the black box in order to generalize a recent linear-timealgorithm for multiple-source shortest paths in unweighted undirected planargraphs to work in arbitrary orientable surfaces. Our algorithm runs in $O(g^2 n\log g)$ time in this setting, and it can be used to give improved linear timealgorithms for several problems in unweighted undirected surface embeddedgraphs of constant genus including the computation of minimum cuts, shortesttopologically non-trivial cycles, and minimum homology bases.

Holiest Minimum-Cost Paths and Flows in Surface Graphs