Maximum Flows by Incremental Breadth-First Search
Autor: | Andrew V. Goldberg, Sagi Hed, Robert E. Tarjan, Haim Kaplan, Renato F. Werneck |
---|---|
Rok vydání: | 2011 |
Předmět: | |
Zdroj: | Algorithms – ESA 2011 ISBN: 9783642237188 ESA |
DOI: | 10.1007/978-3-642-23719-5_39 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |