Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Xiao, Mingyu; Nagamochi, Hiroshi https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-68311
URL:

;

A Linear-Time Algorithm for Integral Multiterminal Flows in Trees

pdf-format:


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 cut-system 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 cut-system 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 cut-system 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 cut-system so that not only a maximum integral multiflow but also a minimum cut-system 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 Linear-Time Algorithm  for Integral Multiterminal Flows in Trees}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{62:1--62:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6831},
  URN =		{urn:nbn:de:0030-drops-68311},
  doi =		{10.4230/LIPIcs.ISAAC.2016.62},
  annote =	{Keywords: Multiterminal flow; Maximum flow; Minimum Cut; Trees; Linear-time algorithms}
}

Keywords: Multiterminal flow; Maximum flow; Minimum Cut; Trees; Linear-time algorithms
Seminar: 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Issue date: 2016
Date of publication: 07.12.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI