文献

J-GLOBAL ID：201602248568058692   整理番号：16A1312494

Ford-Fulkerson最大流手順が停止に失敗する最も単純かつ小さいネットワーク

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

著者 (1件)： Takahashi Toshihiko (Institute of Natural Science and Technology, Academic Assembly, Niigata University)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 24  号： 2  ページ： 390-394(J-STAGE)  発行年： 2016年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： Ford-Fulkerson標識法は最大ネットワークフローの古典的アルゴリズムである。標識法はその端部容量が積分(または等量的に有理数)であるネットワークを常に停止する。他方,ネットワークが無理数容量の端部を持つ場合は停止に失敗する。Ford-Fulkersonはまた,標識法が停止に失敗するようなネットワークの事例を付与した。しかし,彼らの事例は10の頂点と48の端部を持ち,流れ拡大が少々複雑である。過去により単純な事例が出版された。1995年に,Zwickは6頂点と9端部の2つのネットワーク,および6頂点と8端部の1つのネットワークを付与した。後者は最小であるが,無理数容量の計算はある程度の工数を必要とする。従って,彼は後者を最も単純と判定した。本論文では,Zwickの文脈で最も単純かつ小さいネットワークを示した。更に,筆者らの事例では以前の事例全てができないのに対して,無理数端部容量を任意に割付けできる。これは多くの実数値ネットワークが停止に失敗することを示唆する。(翻訳著者抄録)

シソーラス用語： *最大流問題 ,  *アルゴリズム ,  *道【グラフ】 ,  *連分数 ,  Euclid空間 ,  定理 ,  事例研究 ,  標識法 ,  有理数 ,  ネットワーク ,  積分 ,  頂点 ,  端部 ,  停止問題
準シソーラス用語： Ford-Fulkersonアルゴリズム ,  流れ拡大経路 ,  無限連分数 ,  ネットワークフロー

著者キーワード (4件)： maximum flow ,  Ford-Fulkerson algorithm ,  flow augmenting path ,  infinite continued fraction

分類 (2件)： ネットワーク法  (KA03040X) ,  計算理論  (JB02000A)

引用文献 (16件)：

• [1] Ford, L.R. and Fulkerson, D.R.: Flows in Networks, Princeton University Press (1962).
• [2] Dinic, E.A.: Algorithm for solution of a problem of maximum flow in a network with power estimation, Soviet Mathematics Doklady, Vol.11, pp.1277-1280 (1970).
• [3] Takagi, T.: Elementary Number Theory Lecture - Second Edition, Kyoritsu Shuppan Co., Ltd. (1971) (in Japanese).
• [4] Edmonds, J. and Karp, R.M.: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the Association for Computing Machinery, Vol.19, pp.248-264 (1972).
• [5] Lawler, E.L.: Combinatorial Optimization: Networks and Matroid, Holt, Rinehart and Winston (1976).

タイトルに関連する用語 (2件)： 手順 ,  失敗