@inproceedings{3017ca91a9cb4ffe845f6491a24dbb79,
title = "Faster and more dynamic maximum flow by incremental breadth-first search",
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.",
author = "Goldberg, {Andrew V.} and Sagi Hed and Haim Kaplan and Pushmeet Kohli and Tarjan, {Robert E.} and Werneck, {Renato F.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015.; 23rd European Symposium on Algorithms, ESA 2015 ; Conference date: 14-09-2015 Through 16-09-2015",
year = "2015",
doi = "10.1007/978-3-662-48350-3_52",
language = "English (US)",
isbn = "9783662483497",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "619--630",
editor = "Nikhil Bansal and Irene Finocchi",
booktitle = "Algorithms – ESA 2015 - 23rd Annual European Symposium, Proceedings",
address = "Germany",
}