The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate

• Item type: Journal(1)
• 公開日: 2016-03-15
• タイトル: The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate
• タイトル / 言語: en
• タイトル: The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] maximum flow, Ford-Fulkerson algorithm, flow augmenting path, infinite continued fraction
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Institute of Natural Science and Technology, Academic Assembly, Niigata University
• 著者所属(英): en
• 著者所属(英): Institute of Natural Science and Technology, Academic Assembly, Niigata University
• 著者名: Toshihiko, Takahashi
• 著者名(英): Toshihiko, Takahashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 57, 号 3, 発行日 2016-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764