Let G = (V, E) be a digraph with disjoint sets of sources S (C) V and sinks T (C) V endowed with an S-T flow f : E → Z_+. 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 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).
展开▼
