The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate

The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate

0.00 Avg rating0 Votes
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:
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.

Reviews

Required fields are marked *. Your email address will not be published.