Xiao, Mingyu ;
Nagamochi, Hiroshi
A LinearTime Algorithm for Integral Multiterminal Flows in Trees
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}
}
07.12.2016
Keywords: 

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

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

Issue date: 

2016 
Date of publication: 

07.12.2016 