論文

査読有り
1994年12月

IMPLEMENTING AN EFFICIENT MINIMUM CAPACITY CUT ALGORITHM

MATHEMATICAL PROGRAMMING
  • H NAGAMOCHI
  • ,
  • T ONO
  • ,
  • T IBARAKI

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.

リンク情報
DOI
https://doi.org/10.1007/BF01582226
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:A1994PY57500002&DestApp=WOS_CPL
ID情報
  • DOI : 10.1007/BF01582226
  • ISSN : 0025-5610
  • Web of Science ID : WOS:A1994PY57500002

エクスポート
BibTeX RIS