著者

高橋 俊彦

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. CST, コンカレント工学 (ISSN:09135685)

巻号頁・発行日

vol.110, no.284, pp.25-30, 2010-11-11

参考文献数

14

---

Ford and Fulkersonのラベリング法(labeling method)はネットワークの最大フローを求める古典的アルゴリズムである.このアルゴリズムは,ネットワークの辺容量がすべて整数(有理数)の場合に停止性が保証されるが,ネットワークが無理数容量の辺を持つ場合,フロー増加パスの選び方によっては終了しないことがある.現在までに,そのようなネットワークの例が幾つか示されているが,いずれも無理数容量の辺の容量は特定の値であった.本報告では,最簡かつ最小であり,さらに無理数の容量の値が任意であるようなネットワークを与える.この例は実数値容量ネットワークの多くがフロー増加の無限系列を持つことを示唆する.