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
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
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).