Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331345 | Information Processing Letters | 2005 | 7 Pages |
Abstract
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{ν,n2/3,m1/2}m) time, where ν is the size of a minimum (s,t)-cut. In this paper, we define the non-eulerianness μ as the sum of |#incoming edges at uâ#outgoing edges at u| over all uâVâ{s,t}, and prove that a minimum (s,t)-cut in D can be obtained in O(min{m+ν(ν+μ)1/2n,(ν+μ)1/6nm2/3}) time. This outperforms the previous algorithm when D is a dense digraph with small μ.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hiroshi Nagamochi,