2026-03-12T23:52:46Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00158146 2025-01-20T06:55:30Z 581:8417:8420

The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate Toshihiko, Takahashi Toshihiko, Takahashi [一般論文] maximum flow, Ford-Fulkerson algorithm, flow augmenting path, infinite continued fraction 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. \n------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.24(2016) No.2 (online) DOI　http://dx.doi.org/10.2197/ipsjjip.24.390 ------------------------------ 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. \n------------------------------ This is a preprint of an article intended for publication Journal of Information Processing(JIP). This preprint should not be cited. This article should be cited as: Journal of Information Processing Vol.24(2016) No.2 (online) DOI　http://dx.doi.org/10.2197/ipsjjip.24.390 ------------------------------ journal article 2016-03-15 application/pdf 情報処理学会論文誌 3 57 1882-7764 AN00116647 https://ipsj.ixsq.nii.ac.jp/record/158146/files/IPSJ-JNL5703035.pdf eng