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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Let $$G$$G be a directed graph with $$n$$n vertices embedded on an orientable surface of genus $$g$$g with two designated vertices $$s$$s and $$t$$t. We show that computing the number of minimum $$(s,t)$$(s,t)-cuts in $$G$$G is fixed-parameter tractable in $$g$$g. Specifically, we give a $$2^{O(g)} n^2$$2O(g)n2 time algorithm for this problem. Our algorithm requires counting sets of cycles in a particular integer homology class. That we can count these cycles is an interesting result in itself as there are no prior results that are fixed-parameter tractable and deal directly with integer homology. We also describe an algorithm which, after running our algorithm to count minimum cuts once, can sample an $$(s,t)$$(s,t)-minimum cut uniformly at random in $$O(n \\log n)$$O(nlogn) time per sample.

Counting and Sampling Minimum Cuts in Genus $$g$$ g Graphs