2000年
A fast algorithm for computing minimum 3-way and 4-way cuts
Mathematical Programming, Series B
- ,
- 巻
- 88
- 号
- 3
- 開始ページ
- 507
- 終了ページ
- 520
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/PL00011383
- 出版者・発行元
- Elsevier
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(nk-1 F(n, m)) = O(mnk log(n2/m)) time and O(n2) 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 Õ(mn3) for weighted graphs, but improves the bound Õ(mn3) to O(n2 F(n, m)) = O(min{mn8/3, m3/2n2}) for unweighted graphs. The bound Õ(mn4) for k = 4 improves the previous best randomized bound Õ(n6) (for m = o(n2)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system.
- リンク情報
- ID情報
-
- DOI : 10.1007/PL00011383
- ISSN : 0025-5610
- J-Global ID : 200902192363018635
- SCOPUS ID : 4243094422