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/

Zendy Plus

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

Zendy Tools

Zendy Open

Let $G=(V,E)$ be a supply graph and $H=(V,F)$ a demand graph defined on thesame set of vertices. An assignment of capacities to the edges of $G$ anddemands to the edges of $H$ is said to satisfy the \emph{cut condition} if forany cut in the graph, the total demand crossing the cut is no more than thetotal capacity crossing it. The pair $(G,H)$ is called \emph{cut-sufficient} iffor any assignment of capacities and demands that satisfy the cut condition,there is a multiflow routing the demands defined on $H$ within the network withcapacities defined on $G$. We prove a previous conjecture, which states thatwhen the supply graph $G$ is series-parallel, the pair $(G,H)$ iscut-sufficient if and only if $(G,H)$ does not contain an \emph{odd spindle} asa minor; that is, if it is impossible to contract edges of $G$ and delete edgesof $G$ and $H$ so that $G$ becomes the complete bipartite graph $K_{2,p}$, with$p\geq 3$ odd, and $H$ is composed of a cycle connecting the $p$ vertices ofdegree 2, and an edge connecting the two vertices of degree $p$. We furtherprove that if the instance is \emph{Eulerian} --- that is, the demands andcapacities are integers and the total of demands and capacities incident toeach vertex is even --- then the multiflow problem has an integral solution. Weprovide a polynomial-time algorithm to find an integral solution in this case.In order to prove these results, we formulate properties of tight cuts (cutsfor which the cut condition inequality is tight) in cut-sufficient pairs. Webelieve these properties might be useful in extending our results to planargraphs.

When the Cut Condition is Enough: A Complete Characterization for Multiflow Problems in Series-Parallel Networks