Skip to main content

Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search

Author(s): Goldberg, Andrew V; Hed, Sagi; Kaplan, Haim; Kohli, Pushmeet; Tarjan, Robert E; et al

To refer to this page use:
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.
Publication Date: 2015
Citation: Goldberg, Andrew V., Sagi Hed, Haim Kaplan, Pushmeet Kohli, Robert E. Tarjan, and Renato F. Werneck. "Faster and More Dynamic Maximum Flow by Incremental Breadth-First Search." In Algorithms-ESA (2015): pp. 619-630. doi:10.1007/978-3-662-48350-3_52
DOI: 10.1007/978-3-662-48350-3_52
ISSN: 0302-9743
EISSN: 1611-3349
Pages: 619 - 630
Type of Material: Conference Article
Journal/Proceeding Title: Algorithms-ESA
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.