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

✍ Scribed by Torben Hagerup; Jyrki Katajainen; Naomi Nishimura; Prabhakar Ragde

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 417 KB
• Volume: 57
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1998.1592

✦ Synopsis

We show that if a flow network has k inputÂ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 2 k +1 inequalities in k variables representing flow values at the terminals, and a mimicking network with at most 2 2 k vertices 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 constant k, the sequential algorithm runs in O(n) time on n-vertex networks, and the parallel algorithm runs in O(log n) time on an EREW PRAM with O(nÂlog n) processors if an explicit tree decomposition of the network of size O(n) is given; if not, known algorithms can compute such a tree decomposition in O((log n) 2 ) time using O(nÂ(log n) 2 ) processors.