| Presentation | 2010-11-18 The simplest and smallest network on which the Ford-Fulkerson maximum flow procedure may fail to terminate Toshihiko TAKAHASHI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Ford-Fulkerson's labeling method is a classic algorithm for maximum network flows. The labeling method always terminates on networks with integral (rational) capacities. On the other hand, it might fail to terminate if networks have an edge of an irrational capacity. All the examples of such networks ever published have some special irrational edge capacities. In this report, we introduce the simplest and smallest example with an edge of arbitrary irrational capacity. This example suggests that many networks with real-valued edge capacities have infinite sequences of flow augmentations. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Maximum flow / Ford-Fulkerson algorithm / Labeling method / Euclidean algorithm |
| Paper # | CAS2010-69,CST2010-42 |
| Date of Issue |
| Conference Information | |
| Committee | CAS |
|---|---|
| Conference Date | 2010/11/11(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Circuits and Systems (CAS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | The simplest and smallest network on which the Ford-Fulkerson maximum flow procedure may fail to terminate |
| Sub Title (in English) | |
| Keyword(1) | Maximum flow |
| Keyword(2) | Ford-Fulkerson algorithm |
| Keyword(3) | Labeling method |
| Keyword(4) | Euclidean algorithm |
| 1st Author's Name | Toshihiko TAKAHASHI |
| 1st Author's Affiliation | Institute of Natural Science and Technology, Academic Assembly, Niigata University() |
| Date | 2010-11-18 |
| Paper # | CAS2010-69,CST2010-42 |
| Volume (vol) | vol.110 |
| Number (no) | 283 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |