A fast algorithm for computing minimum 3-way and 4-way cuts |
| |
Authors: | Hiroshi Nagamochi Toshihide Ibaraki |
| |
Institution: | (1) Department of Information and Computer Sciences, Toyohashi University of Technology, Tempaku, Toyohashi, Aichi 441-8580 Japan, e-mail: naga@ics.tut.ac.jp, JP;(2) Department of Applied Mathematics and Physics, Kyoto University, Kyoto 606-8501 Japan, e-mail: ibaraki@i.kyoto-u.ac.jp, JP |
| |
Abstract: | For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n
k-1
F(n,m))=O(mn
k
log(n
2
/m)) time and O(n
2) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn
3) for weighted graphs, but improves the bound ?(mn
3) to O(n
2
F(n,m))=O(min{mn
8/3,m
3/2
n
2}) for unweighted graphs. The bound ?(mn
4) for k=4 improves the previous best randomized bound ?(n
6) (for m=o(n
2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.
Received: April 1999 / Accepted: February 2000?Published online August 18, 2000 |
| |
Keywords: | : minimum cuts – graphs – hypergraphs – k-way cuts – polynomial algorithm – submodular function |
本文献已被 SpringerLink 等数据库收录! |
|