Article ID: | iaor19982970 |
Country: | United States |
Volume: | 148 |
Issue: | 1 |
Start Page Number: | 165 |
End Page Number: | 170 |
Publication Date: | Jan 1995 |
Journal: | Theoretical Computer Science |
Authors: | Zwick Uri |
It is widely known that the Ford–Fulkerson procedure for finding the maximum flow in a network need not terminate if some of the capacities of the network are irrational. Ford and Fulkerson gave as an example a network with 10 vertices and 48 edges on which their procedure may fail to halt. We construct much smaller and simpler networks on which the same may happen. Our smallest network has only 6 vertices and 8 edges. We show that it is the smallest example possible.