論文

査読有り
2016年3月15日

The simplest and smallest network on which the ford-fulkerson maximum flow procedure may fail to terminate

Journal of Information Processing
  • Toshihiko Takahashi

24
2
開始ページ
390
終了ページ
394
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.2197/ipsjjip.24.390
出版者・発行元
Information Processing Society of Japan

Ford and Fulkerson’s labeling method is a classic algorithm for maximum network flows. The labeling method always terminates for networks whose edge capacities are integral (or, equivalently, rational). On the other hand, it might fail to terminate if networks have an edge with an irrational capacity. Ford and Fulkerson also gave an example of such networks on which the labeling method might fail to terminate. However, their example has 10 vertices and 48 edges and the flow augmentation is a little bit complicated. Simpler examples have been published in the past. In 1995, Zwick gave two networks with 6 vertices and 9 edges and one network with 6 vertices and 8 edges. The latter is the smallest, however, the calculation of the irrational capacity requires some effort. Thus, he called the former the simplest. In this paper, we show the simplest and smallest network in Zwick’s context. Moreover, the irrational edge capacity of our example can be arbitrarily assigned while those in the all previous examples are not. This suggests that many real-valued networks might fail to terminate.

リンク情報
DOI
https://doi.org/10.2197/ipsjjip.24.390
ID情報
  • DOI : 10.2197/ipsjjip.24.390
  • ISSN : 1882-6652
  • ISSN : 0387-5806
  • SCOPUS ID : 84961149409

エクスポート
BibTeX RIS