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

31 Scopus citations


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
Number of pages12
ISBN (Print)9783662483497
StatePublished - 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)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other23rd European Symposium on Algorithms, ESA 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


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