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

Autor:	Renato F. Werneck, Haim Kaplan, Andrew V. Goldberg, Pushmeet Kohli, Robert E. Tarjan, Sagi Hed
Rok vydání:	2015
Předmět:	Polynomial Series (mathematics) Computer science Maximum flow problem Breadth-first search Adjacency list Segmentation Object (computer science) Algorithm Running time
Zdroj:	Algorithms-ESA 2015 ISBN: 9783662483497 ESA
DOI:	10.1007/978-3-662-48350-3_52
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::ef53a977406206503693ebb21c19d7ae https://doi.org/10.1007/978-3-662-48350-3_52 Zobrazit plný text záznamu