On computing minimum (s,t)-cuts in digraphs

Let D = (V, E) be a simple digraph with n vertices and m edges, and s and t be vertices designated as a source and a sink. The currently fastest algorithm that computes a minimum (s, t)-cut in D runs in O(min{nu, n(2/3), m(1/2)}m) time, where v is the size of a minimum (s, t)-cut. In this paper, we define the non-eulerianness it as the sum of \#incoming edges at u - #outgoing edges at u\ over all u is an element of V - {s, t}, and prove that a minimum (s, t)-cut in D can be obtained in O(min{m + nu(nu + mu)(1/2)n, (nu + mu)(1/6)nm(2/3)}) time. This outperforms the previous algorithm when D is a dense digraph with small mu. (C) 2004 Elsevier B.V. All rights reserved.