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.|
|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|
|Pages:||619 - 630|
|Type of Material:||Conference Article|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.