Abstract
In this paper, we study the problem of finding an integral multiflow which maximizes the sum of flow values between every two terminals in an undirected tree with a nonnegative integer edge capacity and a set of terminals. In general, it is known that the flow value of an integral multiflow is bounded by the cut value of a cutsystem which consists of disjoint subsets each of which contains exactly one terminal or has an odd cut value, and there exists a pair of an integral multiflow and a cutsystem whose flow value and cut value are equal; i.e., a pair of a maximum integral multiflow and a minimum cut. In this paper, we propose an O(n)time algorithm that finds such a pair of an integral multiflow and a cutsystem in a given tree instance with n vertices. This improves the best previous results by a factor of Omega(n). Regarding a given tree in an instance as a rooted tree, we define O(n) rooted tree instances taking each vertex as a root, and establish a recursive formula on maximum integral multiflow values of these instances to design a dynamic programming that computes the maximum integral multiflow values of all O(n) rooted instances in linear time. We can prove that the algorithm implicitly maintains a cutsystem so that not only a maximum integral multiflow but also a minimum cutsystem can be constructed in linear time for any rooted instance whenever it is necessary. The resulting algorithm is rather compact and succinct.
BibTeX  Entry
@InProceedings{xiao_et_al:LIPIcs:2016:6831,
author = {Mingyu Xiao and Hiroshi Nagamochi},
title = {{A LinearTime Algorithm for Integral Multiterminal Flows in Trees}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {62:162:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770262},
ISSN = {18688969},
year = {2016},
volume = {64},
editor = {SeokHee Hong},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6831},
URN = {urn:nbn:de:0030drops68311},
doi = {10.4230/LIPIcs.ISAAC.2016.62},
annote = {Keywords: Multiterminal flow; Maximum flow; Minimum Cut; Trees; Lineartime algorithms}
}
Keywords: 

Multiterminal flow; Maximum flow; Minimum Cut; Trees; Lineartime algorithms 
Collection: 

27th International Symposium on Algorithms and Computation (ISAAC 2016) 
Issue Date: 

2016 
Date of publication: 

07.12.2016 