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

It has been previously shown by the authors that a directed graph on alinearly ordered set of edges (ordered graph) with adjacent unique source andsink (bipolar digraph) has a unique fully optimal spanning tree, that satisfiesa simple criterion on fundamental cycle/cocycle directions. This result yields,for any ordered graph, a canonical bijection between bipolar orientations andspanning trees with internal activity 1 and external activity 0 in the sense ofthe Tutte polynomial. This bijection can be extended to all orientations andall spanning trees, yielding the active bijection, presented for graphs in acompanion paper. In this paper, we specifically address the problem of thecomputation of the fully optimal spanning tree of an ordered bipolar digraph.In contrast with the inverse mapping, built by a straightforward single passover the edge set, the direct computation is not easy and had previously beenleft aside. We give two independent constructions. The first one is adeletion/contraction recursion, involving an exponential number of minors. Itis structurally significant but it is efficient only for building the wholebijection (i.e. all images) at once. The second one is more complicated and isthe main contribution of the paper. It involves just one minor for each edge ofthe resulting spanning tree, and it is a translation and an adaptation in thecase of graphs, in terms of weighted cocycles, of a general geometrical linearprogramming type algorithm, which allows for a polynomial time complexity.

Computing the fully optimal spanning tree of an ordered bipolar directed graph