Maximum flows by incremental breadth-First search

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

48 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAlgorithms, ESA 2011 - 19th Annual European Symposium, Proceedings
Pages457-468
Number of pages12
DOIs
StatePublished - Sep 20 2011
Event19th Annual European Symposium on Algorithms, ESA 2011 - Saarbrucken, Germany
Duration: Sep 5 2011Sep 9 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6942 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other19th Annual European Symposium on Algorithms, ESA 2011
CountryGermany
CitySaarbrucken
Period9/5/119/9/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Maximum flows by incremental breadth-First search'. Together they form a unique fingerprint.

  • Cite this

    Goldberg, A. V., Hed, S., Kaplan, H., Tarjan, R. E., & Werneck, R. F. (2011). Maximum flows by incremental breadth-First search. In Algorithms, ESA 2011 - 19th Annual European Symposium, Proceedings (pp. 457-468). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6942 LNCS). https://doi.org/10.1007/978-3-642-23719-5_39