Algorithms in a Nutshell

Overview | 227

Network Flow

Algorithms

One way to explain how these specialized problems are solved is to describe the

relationship between network flow problems. Figure 8-1 shows the relationships

between these problems in thin, labeled rectangles, with brief descriptions in the

larger boxes. A more general instance of a problem is related to a more specific

instance of the problem by a directed edge. For example, the Transportation

problem is a specialized instance of the Transshipment problem because transpor-

tation graphs do not contain intermediate transshipment nodes. Thus a program

that solves the Transshipment problem can be immediately applied to solve

Transportation problems.

In this chapter we present the FORD-FULKERSONalgorithm, which solves the

Maximum Flow problem. FORD-FULKERSONcan be immediately applied to solve

Bipartite Matching problems, as shown in Figure 8-1. Upon further reflection, the

Figure 8-1. Relationship between network flow problems

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