Skip to main content

Maximum Flows by Incremental Breadth-First Search

Author(s): Goldberg, Andrew V; Hed, Sagi; Kaplan, Haim; Tarjan, Robert E; Werneck, Renato F

To refer to this page use:
Abstract: 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 Date: 2011
Citation: Goldberg, Andrew V., Sagi Hed, Haim Kaplan, Robert E. Tarjan, and Renato F. Werneck. "Maximum Flows by Incremental Breadth-First Search." In European Symposium on Algorithms (2011): pp. 457-468. doi:10.1007/978-3-642-23719-5_39
DOI: 10.1007/978-3-642-23719-5_39
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 457 - 468
Type of Material: Conference Article
Journal/Proceeding Title: European Symposium on Algorithms
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.