Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-010 (April 01, 2011)

Linear-time Algorithms for Multiterminal Flows in Trees
by Mingyu Xiao, Hiroshi Nagamochi

pdf File


In this paper, we study the problem of finding a multiflow which maximizes the sum of flow values between every two terminals in an undirected tree with a nonnegative edge capacity and a set of terminals. We show that a multiflow in an undirected tree can be characterized by a local structure, called ``balancedness." Based on the characterization, we design a simple linear-time and linear-space algorithm for finding a maximum multiflow for our problem. Then we present a dynamic programming approach and give an linear-time and linear-space algorithm for finding a maximum integer multiflow when all edge capacities are integers. Our algorithms improve the best previous results by a factor of $\Omega (n)$. We also derive an upper and lower bounds on the number of pairs of terminals between which a positive amount of flow is sent in a given multiflow in a tree and present an linear-time and linear-space algorithm to represent the multiflow in a decomposition method (terminals pairs together with value of positive flow between them).