@ytyoun

The Smallest Networks on which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate

. Theoretical Computer Science, 148 (1): 165--170 (1995)
DOI: 10.1016/0304-3975(95)00022-O

Abstract

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.

Links and resources

Tags