Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Maximum Flows by Incremental Breadth-First Search

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.


Publication typeInproceedings
Published in19th European Symposium on Algorithms (ESA 2011)
PublisherSpringer Verlag
> Publications > Maximum Flows by Incremental Breadth-First Search