On Fulkerson's Conjecture About Consistent Labeling Processes

Fulkerson conjectured that any consistent labeling process implies a polynomial time bound for the Ford-Fulkerson max-flow algorithm. The conjecture is disproved by means of a sequence of networks requiring an exponential number of augmentations, resulting from a consistent labeling process. On the other hand, it is shown that any consistent labeling process yields an algorithm which runs in time O[Min(V!, 3^E)]. This result is stronger than A. Tucker's which states that consistency implies a finite number of augmentations.