Maximum Flows by Incremental Breadth-First Search

  • Andrew Goldberg ,
  • Sagi Hed ,
  • Haim Kaplan ,
  • Robert E. Tarjan ,
  • Renato Werneck

19th European Symposium on Algorithms (ESA 2011) |

Published by Springer Verlag

Download BibTex

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.