Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: In an undirected graph, the maximum matching problem requires finding a set of nonadjacent edges having the largest total size or largest total weight. This graph optimization problem arises in a number of applications, often involving the optimal pairing of a set of objects. This section reviews the basic concepts, theory, and algorithms for matchings in bipartite and more general networks.

Key Words: assignment, augmenting path, matching, perfect matching, weighted matching