.png){kind=icon}
.png){kind=icon}
Return
Integral biflow maximization
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jctb.2025.12.006.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Let G = (V, E) be a graph with four distinguished vertices, two sources s(1), s(2) and two sinks t(1), t(2), let c : E -> Z+ be a capacity function, and let P be the set of all simple paths in G from s(1) to t(1) or from s(2) to t(2). A biflow (or 2-commodity flow) in G is an assignment f: P -> R(+)such that to be Sigma(e is an element of Q is an element of p),f (Q) <= c(e) for all e is an element of E, whose value is defined Sigma(Q is an element of 7), f (Q). A bicut in G is a subset K of E that contains at least one edge from each member of P, whose capacity is Sigma(e is an element of K) c(e). In 1977 Seymour characterized, in terms of forbidden structures, all graphs G for which the maxbiflow (integral) min-bicut theorem holds true (that is, the maximum value of an integral biflow is equal to the minimum capacity of a bicut for every capacity function c); such a graph G is referred to as a Seymour graph. Nevertheless, his proof is not algorithmic in nature. In this paper we present a combinatorial polynomial-time algorithm for finding maximum integral biflows in Seymour graphs, which relies heavily on a structural description of such graphs. (c) 2026 Published by Elsevier Inc.
Keywords:
Biflow
Bicut
Algorithm
Structure
Characterization
Journal
J
IF:
1.2
Papers:
48
Citations:
0