226Chapter 8. Network Flow Algorithms.........................................................................................................................................
8
Network Flow Algorithms
Overview
There are numerous problems that can be viewed as a network of vertices and
edges, with a capacity associated with each edge over which commodities flow.
The algorithms found in this chapter are, in many ways, the direct product of the
need to solve these specific classes of problems. Ahuja (1993) contains an exten-
sive discussion on numerous applications of network flow algorithms:
Assignment
Given a set of tasks to be carried out by a set of employees, find an assign-
ment that minimizes the overall expense when different employees may cost
different amounts based upon the task to which they are assigned.
Bipartite Matching
Given a set of applicants who have been interviewed for a set of job open-
ings, find a matching that maximizes the number of applicants selected for
jobs for which they are qualified.
Transportation
Determine the most cost-effective way to ship goods from a set of supplying
factories to a set of retail stores selling these goods.
Transshipment
Determine the most cost-effective way to ship goods from a set of supplying
factories to a set of retail stores selling these goods, while potentially using a
set of warehouses as intermediate stations.
Maximum Flow
Given a network that shows the potential capacity over which goods can be
shipped between two locations, compute the maximum flow supported by
the network.Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use