Multi-terminal multipath flows: synthesis Original Research Article

Given an undirected network G≡[N,E], a source–sink pair of nodes (s,t) in N, a non-negative number ui,j representing the capacity of edge (i,j) for each (i,j)∈E, and a positive integer q, an “elementary q-path flow” from s to t is defined as a flow of q units from s to t, with one unit of flow along each path in a set of q edge-disjoint s–t paths. A q-path flow from s to t is a non-negative linear combination of elementary q-path flows from s to t. In this paper we provide a strongly polynomial combinatorial algorithm for designing an undirected network with minimum total edge capacity which is capable of meeting, non-simultaneously, a given set of symmetric q-path flow requirements between all pairs of nodes. This extends the previous work on network synthesis.