K-route Flows And Its Variant Algorithm

Let G = (N,A,u) be a network with vertex set N, arcset A, a source vertex s∈N ,a destination vertex t∈N , a finite capacity vector u = {u_ij : (i,j)∈A} and a positive integer K. An elementary K-flowis a flow of K units from source vertex s∈N to destination vertex t∈N such that the flow on each arc is 0 or 1.A K-route flow is a flow from s to t that may be expressed as a nonnegative linear sum of elementary K-flows. Therefore, the K-route flow problem generalizes the ordinary maximum flow problem by seeking a maximum flow from s to t subject to not only the regular flow conservation constraints at the vertices (except s and t) and the flow capacity constraints at the arcs, but also the extra constraints that any flow must be routed along K arc-disjoint s-t paths. In this article, We present a new combinatorial algorithm for this problem. We theoretically discuss iteration number of this new algorithm is no more than Kishimoto's and Newton's, but is no less than primal-dual algorithm's. Last, we briefly introduce K- route flows' transformation from arc-flows into path-flows.