Flow Decompositions in External Memory

Lecture Notes in Computer Science. 2013. Vol. 7741. P. 146–156.

Maxim Babenko

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 → Z+. It is a well-known fact that f decomposes into a sum_st(fst) of s–t flows fst 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 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 V 2 E ) I/Os and the second one takes O(Sort(E) log U) expected I/Os (where U denotes the maximum value of f).

Ключевые слова: digraph, decomposition method, external memory algorithms