Faster and more dynamic maximum flow by incremental breadth-first search

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

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

12 Scopus citations

Abstract

We introduce the Excesses Incremental Breadth-First Search (Excesses IBFS) algorithm for maximum flow problems. We show that Excesses IBFS has the best overall practical performance on real-world instances, while maintaining the same polynomial running time guarantee of O(mn2) as IBFS, which it generalizes. Some applications, such as video object segmentation, require solving a series of maximum flow problems, each only slightly different than the previous. Excesses IBFS naturally extends to this dynamic setting and is competitive in practice with other dynamic methods.

Original languageEnglish (US)
Title of host publicationAlgorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings
EditorsNikhil Bansal, Irene Finocchi
PublisherSpringer Verlag
Pages619-630
Number of pages12
ISBN (Print)9783662483497
DOIs
StatePublished - Jan 1 2015
Event23rd European Symposium on Algorithms, ESA 2015 - Patras, Greece
Duration: Sep 14 2015Sep 16 2015

Publication series

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

Other

Other23rd European Symposium on Algorithms, ESA 2015
CountryGreece
CityPatras
Period9/14/159/16/15

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Faster and more dynamic maximum flow by incremental breadth-first search'. Together they form a unique fingerprint.

  • Cite this

    Goldberg, A. V., Hed, S., Kaplan, H., Kohli, P., Tarjan, R. E., & Werneck, R. F. (2015). Faster and more dynamic maximum flow by incremental breadth-first search. In N. Bansal, & I. Finocchi (Eds.), Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings (pp. 619-630). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9294). Springer Verlag. https://doi.org/10.1007/978-3-662-48350-3_52