Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth

摘要

We show that if a flow network haskinput/output terminals (for the traditional maximum-flow problem,k=2), its external flow pattern (the possible values of flow into and out of the terminals) has two characterizations of size independent of the total number of vertices: a set of 2k+1 inequalities inkvariables representing flow values at the terminals, and a mimicking network with at most 22kvertices and the same external flow pattern as the original network. For the case in which the underlying graph has bounded treewidth, we present sequential and parallel algorithms that can compute these characterizations as well as a flow consistent with any desired feasible external flow (including a maximum flow between two given terminals). For constantk, the sequential algorithm runs inO(n) time onn-vertex networks, and the parallel algorithm runs inO(log n) time on an EREW PRAM withO(n/log n) processors if an explicit tree decomposition of the network of sizeO(n) is given; if not, known algorithms can compute such a tree decomposition inO((log n)2) time usingO(n/(log n)2) processors.