Chapter 7

• Matching in bipartite graphs can model situations in which objects are being assigned to other objects
  • Nodes in X represent jobs, and the nodes in Y represent machines, and an edge (xi,yj) indicates that machine yj is capable of processing job xi.
• Perfect Matching: a way of assigning each job to a machine that can process it
  • Property that each machine is assigned exactly one job
• One of the oldest problems in combinatorial algorithms: determining the size of the largest matching in a bipartite graph G
  • Network Flow Problems: includes the Bipartite Matching Problem as a special case

===== 7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm