Network Flows: Theory, Algorithms, and Applications

By Ravindra K. Ahuja, T. Magnanti, James B. Orlin. 1993

A comprehensive introduction to network flows that brings together the classic and the contemporary aspects of the field, and provides an integrative view of theory, algorithms, and applications. presents in-depth, self-contained treatments of shortest path, maximum flow, and minimum cost flow problems, including descriptions of polynomial-time algorithms for these core models. emphasizes powerful algorithmic strategies and analysis tools such as data scaling, geometric improvement arguments, and potential function arguments. provides an easy-to-understand descriptions of several important data structures, including d-heaps, Fibonacci heaps, and dynamic trees. devotes a special chapter to conducting empirical testing of algorithms. features over 150 applications of network flows to a variety of engineering, management, and scientific domains. contains extensive reference notes and illustrations.

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

Mathematical optimization in classification and regression trees (2021, methodology): “A sink node is added to the tree, yielding a directed acyclic graph (Ahuja et al. 1993).”
Sinkhorn Distances: Lightspeed Computation of Optimal Transport (2013, methodology): “An optimal table P ⋆ for this problem can be obtained, among other approaches, with the network simplex (Ahuja et al., 1993, §9).”
Community detection in graphs (2009, methodology): “The maximum flow can be calculated in a time O(m), for a graph with m 13 edges, using techniques like the augmenting path algorithm (Ahuja et al., 1993).”
Optimal Transport for Domain Adaptation (2014, neutral): “While the family of transformation that an OT formulation can recover is wide, we provide a proof that, for some simple afﬁne transformations of discrete distributions, our OT so-lution is able to match source and target examples exactly.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, neutral): “, [99, 2] for more details).”
Dynamic lot size problems with one-way product substitution (2005, background): “Hence, all gtj(τ, π ) values can be determined by solving an all-pairs shortest path problem, which requires a running time of O((mT)3) (Ahuja et al., 1993).”
Multi-constrained optimal path selection (2001, methodology): “For the MCOP problem is known as the restricted shortest path (RSP) problem, which is NP-complete [ 15 ].”
Selected Topics in Column Generation (2002, background): “Consider the one-dimensional cutting-stock problem, the classical example in column generation introduced by Gilmore and Gomory (1961).”
The Structure and Function of Complex Networks (2003, methodology): “, maximum flow) [7], and weighted path counts between vertices.”
The Web as a Parallel Corpus (2003, methodology): “The assumption reduces the formula for tsim to tsim = number of two-word links in best matching number of links in best matching ( 4 ) The key reason to compute tsim under the equiprobability assumption is that we need not compute the MWBM, but may ﬁnd just the maximum cardinality bipartite matching”
Linear Programming: Foundations and Extensions (1998, methodology): “(1977), Kennington & Helgason (1980), Jensen & Barnes (1980), Bertsekas (1991), and Ahuja et al. (1993). The two “original” algorithms for solving minimum-cost network flow problems are the network simplex method developed by Dantzig (1951a) and the primal–dual method developed by Ford & Fulkerson (”
Optimization of supply chain networks with inclusion of labor: Applications to COVID-19 pandemic disruptions (2021, unknown): “…as noted in Qiang and Nagurney (2012), where a bicriteria supply chain network performance measure was introduced in the case of disasters, we can first solve the maximum flow problem (cf. Ahuja et al. (1993)), which is a well-known classical network optimization problem in operations research.”
Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. (2000, methodology): “Instead we use Dijkstra’s algorithm [67], which calculates all distances from a given starting vertex i as follows.”
Explaining code for publication (2003, background): “Some (e.g., [ 17 ]) provide a mixture of mathematics and English, and provide code for most of the relevant routines, but the code is difficult to translate into complete and correct algorithms (e.g., because what may look like a simple variable is in fact a non-trivialdynamically bound expression).”
A survey of recent developments in multiobjective optimization (2007, background): “These algorithms can be found in many textbooks on graph theory and network flows, for example, in Ahuja et al. (1993) .”
Restoration of Services in Interdependent Infrastructure Systems: A Network Flows Approach (2007, methodology): “These additional requirements of multicommodity systems must be accounted for [ 39 ].”