1994年12月
IMPLEMENTING AN EFFICIENT MINIMUM CAPACITY CUT ALGORITHM
MATHEMATICAL PROGRAMMING
- ,
- ,
- 巻
- 67
- 号
- 3
- 開始ページ
- 325
- 終了ページ
- 341
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1007/BF01582226
- 出版者・発行元
- ELSEVIER SCIENCE BV
In this paper, we present an efficient implementation of the O(mn+n(2) log n) time algorithm originally proposed by Nagamochi and Ibaraki (1992) for computing the minimum capacity cut of an undirected network. To enhance computation, various ideas are added so that it can contract as many edges as possible in each iteration, To evaluate the performance of the resulting implementation, we conducted extensive computational experiments, and compared the results with that of Padberg and Rinaldi's algorithm (1990), which is currently known as one of the practically fastest programs for this problem. The results indicate that our program is considerably faster than Padberg and Rinaldi's program, and its running time is not significantly affected by the types of the networks being solved.
- リンク情報
- ID情報
-
- DOI : 10.1007/BF01582226
- ISSN : 0025-5610
- Web of Science ID : WOS:A1994PY57500002