Maximum flows by incremental breadth-first search

DOI10.1007/978-3-642-23719-5_39MaRDI QIDQ3092252zbMATH OpenOpenAlexFDO

Authors Andrew V. Goldberg, Sagi Hed, Haim Kaplan, Renato F. Werneck, Robert E. Tarjan

Publication date 16 September 2011

Published in Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-23719-5_39

Mathematics Subject Classification ID

Flows in graphs (05C21) Graph algorithms (graph-theoretic aspects) (05C85) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Machine vision and scene understanding (68T45)

Recommendations

• Faster and more dynamic maximum flow by incremental breadth-first search
• scientific article; zbMATH DE number 1849127
• Simplifying maximum flow computations: the effect of shrinking and good initial flows
• A distributed mincut/maxflow algorithm combining path augmentation and push-relabel
• Combinatorial continuous maximum flow

Cited in

(12)

• An incremental algorithm for the maximum flow problem
• A distributed mincut/maxflow algorithm combining path augmentation and push-relabel
• Combinatorial continuous maximum flow
• Efficient implementation of a synchronous parallel push-relabel algorithm
• Faster and more dynamic maximum flow by incremental breadth-first search
• scientific article; zbMATH DE number 1849127 (Why is no real title available?)
• Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• Maximal flow in branching trees and binary search trees
• Approximation algorithms for job scheduling with block-type conflict graphs
• Incremental network design with maximum flows
• An exact combinatorial algorithm for minimum graph bisection

This page was built for publication: Maximum flows by incremental breadth-first search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3092252)