A. V. Goldberg, S. Hed, H. Kaplan, R. E. Tarjan, and R. F. Werneck
Maximum flow and minimum s-t cut algorithms are used to solve several fundamental problems in computer vision. These problems have special structure, and standard techniques perform worse than the special-purpose Boykov-Kolmogorov (BK) algorithm. We introduce the incremental breadth-first search (IBFS) method, which uses ideas from BK but augments on shortest paths. IBFS is theoretically justified (runs in polynomial time) and usually outperforms BK on vision problems.
In 19th European Symposium on Algorithms (ESA 2011)
Publisher Springer Verlag