Flow Decompositions in External Memory

Let G = (V,E) be a digraph with disjoint sets of sources S ⊂ V and sinks T ⊂ V endowed with an S–T flow f  : E → ℤ₊. It is a well-known fact that f decomposes into a sum ∑  _st f _st of s–t flows f _st between all pairs of sources s ∈ S and sinks t ∈ T. In the usual RAM model, such a decomposition can be found in \(O(E \log \frac{V^2}{E})\) time. The present paper concerns the complexity of this problem in the external memory model (introduced by Aggarwal and Vitter). The internal memory algorithm involves random memory access and thus becomes inefficient. We propose two novel methods. The first one requires \(O(Sort(E) \log \frac{V^2}{E})\) I/Os and the second one takes O(Sort(E) logU) expected I/Os (where U denotes the maximum value of f).

Authors and Affiliations

1. Moscow State University, Yandex LLC, Russia

   Maxim Babenko

Editors and Affiliations

1. Department of Mathematics and Computer Science, University of Amsterdam, Plantage Muidergracht 24, 1018 TV, Amsterdam, The Netherlands

   Peter van Emde Boas

2. Informatics Institute, Intelligent Systems Lab Amsterdam, University of Amsterdam, Science Park 904, 1098 XH, Amsterdam, The Netherlands

   Frans C. A. Groen

3. Department of Civil Engineering and Computer Science, University of Rome Tor Vergata, Via del Politecnico 1, 00133, Rome, Italy

   Giuseppe F. Italiano

4. Institute of Computing Science, Poznan University of Technology, ul. Piotrowo 2, 60-965, Poznan, Poland

   Jerzy Nawrocki

5. Hasso-Plattner-Institute for Software Systems Engineering, Prof.-Dr.-Helmert-Str. 2-3, 14482, Potsdam, Germany

   Harald Sack

Reprints and permissions

© 2013 Springer-Verlag Berlin Heidelberg

Policies and ethics