{"created":"2025-01-19T00:31:55.026997+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00158146","sets":["581:8417:8420"]},"path":["8420"],"owner":"11","recid":"158146","title":["The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate"],"pubdate":{"attribute_name":"公開日","attribute_value":"2016-03-15"},"_buckets":{"deposit":"458d4ab5-4922-451b-a47f-72ea68ec6970"},"_deposit":{"id":"158146","pid":{"type":"depid","value":"158146","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate","author_link":["301369","301370"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate"},{"subitem_title":"The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[一般論文] maximum flow, Ford-Fulkerson algorithm, flow augmenting path, infinite continued fraction","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"2016-03-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Institute of Natural Science and Technology, Academic Assembly, Niigata University"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Institute of Natural Science and Technology, Academic Assembly, Niigata University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"publish_status":"0","weko_shared_id":11,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/158146/files/IPSJ-JNL5703035.pdf","label":"IPSJ-JNL5703035.pdf"},"date":[{"dateType":"Available","dateValue":"2018-03-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL5703035.pdf","filesize":[{"value":"224.1 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"5bf8c5d1-535f-4b8a-9753-9cf60dcf9752","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2016 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Toshihiko, Takahashi"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Toshihiko, Takahashi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"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\\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.24(2016) No.2 (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.24.390\n------------------------------","subitem_description_type":"Other"}]},"item_2_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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\\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.24(2016) No.2 (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.24.390\n------------------------------","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2016-03-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicVolumeNumber":"57"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"id":158146,"updated":"2025-01-20T06:55:30.404698+00:00","links":{}}