A new approach to the maximum flow problem

By Andrew Vladislav Goldberg, Robert Endre Tarjan. 1986

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning Optimal Classification Trees: Strong Max-Flow Formulations (2020, background): “2) to add can in general be done by solving a minimum cut problem, for which specialized algorithms exist, see Goldberg and Tarjan (1988) and Hochbaum (2008).”
Community detection in graphs (2009, methodology): “However, there are currently several algorithms able to find fairly good approximations of the modularity maximum in a reasonable time.”
An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision (2001, methodology): “This cost is normally derived from the data term Dp in the energy (1).”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “In terms of running-time complexity, several algorithmic frameworks lead to polynomialtime algorithm: for example, with p vertices and m edges, “push-relabel” algorithms [79] may reach a worst-case complexity of O(p2m1/2).”
Efficient identification of Web communities (2000, background): “the pre- ow push algorithm [25] (considered the fastest in”
Digraphs - theory, algorithms and applications (2002, methodology): “(b) If we always push from a vertex p which has the largest height h(p) among all active vertices, then we obtain an O(n(2) √ m) algorithm [149, 325].”
Minimizing Energies with Hierarchical Costs (2012, methodology): “In practice, this sub-problem is solved by casting it as a graph cut (Greig et al. 1989) and using combinatorial algorithms to compute the optimal binary configuration (e.g. Goldberg and Tarjan 1988; Boykov and Kolmogorov 2004; Strandmark and Kahl 2010).”
Combinatorial optimization and reasoning with graph neural networks (2021, unknown): “This problem inspired a fruitful stream of novel combinatorial algorithms and data structures (Ford and Fulkerson, 1956; Edmonds and Karp, 1972; Dinic, 1970; Sleator and Tarjan, 1983; Goldberg and Tarjan, 1988), with applications stretching far beyond the original intent.”
Reachability and distance queries via 2-hop labels (2002, methodology): “The currently best available time bound for tile problem is O(mnlog(n~/rn)), due to Gallo, Grigoriadis, and Tarjan [3].”
Network Flow Algorithms for Structured Sparsity (2010, unknown): “Then, the second step tries to find a feasible flow of the original problem (4) such that the resulting vector ξ̄ matches γ, which is in fact a max-flow problem [24].”
The Algorithm Design Manual (2020, background): “The fastest known general network flow algorithm runs in O(nm lg(n(2)/m)) time [GT88].”
Optical flow modeling and computation: A survey (2015, background): “The basis of graph cuts is the max-ﬂow/min-cut problem consisting in ﬁnding the optimal path between two nodes in a directed graph, solvable by many algo-rithm in polynomial time [91,102].”