Characterizing the flow equivalent trees of a network

✍ Scribed by David Hartvigsen

• Book ID: 104294104
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 115 KB
• Volume: 128
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00501-2

✦ Synopsis

Consider a connected graph G with positive edge capacities. Gomory and Hu (J. SIAM 9 (1961) 551) showed that there always exists a tree T with positive edge capacities, on the same node set as G, such that the max ow value between any pair of nodes in G is the same as the max ow value between the corresponding pair of nodes in T . Such a tree is called a ow equivalent tree for G and need not be unique. In this paper, we present a "compact" (i.e., polynomial size) characterization of the collection of all ow equivalent trees for a graph G. We also present a polynomial time algorithm for recognizing such representations.