Maximum Flows by Incremental Breadth-First Search
Author(s): Goldberg, Andrew V; Hed, Sagi; Kaplan, Haim; Tarjan, Robert E; Werneck, Renato F
DownloadTo refer to this page use:
http://arks.princeton.edu/ark:/88435/pr1254zFull metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Goldberg, Andrew V | - |
| dc.contributor.author | Hed, Sagi | - |
| dc.contributor.author | Kaplan, Haim | - |
| dc.contributor.author | Tarjan, Robert E | - |
| dc.contributor.author | Werneck, Renato F | - |
| dc.date.accessioned | 2021-10-08T19:47:34Z | - |
| dc.date.available | 2021-10-08T19:47:34Z | - |
| dc.date.issued | 2011 | en_US |
| dc.identifier.citation | Goldberg, Andrew V., Sagi Hed, Haim Kaplan, Robert E. Tarjan, and Renato F. Werneck. "Maximum Flows by Incremental Breadth-First Search." In European Symposium on Algorithms (2011): pp. 457-468. doi:10.1007/978-3-642-23719-5_39 | en_US |
| dc.identifier.issn | 0302-9743 | - |
| dc.identifier.uri | http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.450.1652&rep=rep1&type=pdf | - |
| dc.identifier.uri | http://arks.princeton.edu/ark:/88435/pr1254z | - |
| dc.description.abstract | Maximum flow and minimum s-t cut algorithms are used to solve several fundamental problems in computer vision. These problems have special structure, and standard techniques perform worse than the special-purpose Boykov-Kolmogorov (BK) algorithm. We introduce the incremental breadth-first search (IBFS) method, which uses ideas from BK but augments on shortest paths. IBFS is theoretically justified (runs in polynomial time) and usually outperforms BK on vision problems. | en_US |
| dc.format.extent | 457 - 468 | en_US |
| dc.language.iso | en_US | en_US |
| dc.relation.ispartof | European Symposium on Algorithms | en_US |
| dc.rights | Author's manuscript | en_US |
| dc.title | Maximum Flows by Incremental Breadth-First Search | en_US |
| dc.type | Conference Article | en_US |
| dc.identifier.doi | 10.1007/978-3-642-23719-5_39 | - |
| dc.identifier.eissn | 1611-3349 | - |
| pu.type.symplectic | http://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceeding | en_US |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| MaxFlowsIncrementalBfs.pdf | 192.37 kB | Adobe PDF | View/Download |
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.