%0 Journal Article %1 zwick95 %A Zwick, Uri %D 1995 %J Theoretical Computer Science %K algorithm ford-fulkerson graph.theory max-flow min-cut %N 1 %P 165--170 %R 10.1016/0304-3975(95)00022-O %T The Smallest Networks on which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate %V 148 %X 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.

@article{zwick95, 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. }, added-at = {2016-03-02T14:27:39.000+0100}, author = {Zwick, Uri}, biburl = {https://www.bibsonomy.org/bibtex/230f05a5b6ac4cb1cd70c025ef3382386/ytyoun}, doi = {10.1016/0304-3975(95)00022-O}, interhash = {3b0620592cf5b172155e110fa0573ca1}, intrahash = {30f05a5b6ac4cb1cd70c025ef3382386}, issn = {0304-3975}, journal = {Theoretical Computer Science }, keywords = {algorithm ford-fulkerson graph.theory max-flow min-cut}, number = 1, pages = {165--170}, timestamp = {2016-03-02T14:27:39.000+0100}, title = {The Smallest Networks on which the {Ford-Fulkerson} Maximum Flow Procedure May Fail to Terminate }, volume = 148, year = 1995 }