Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: In an undirected network, the maximum matching problem is to find a set of nonadjacent edges that has the largest total size or weight. This discrete optimization problem arises in a number of applications, often involving the optimal pairing of a set of objects. This section reviews the basic concepts and theory of matchings for both bipartite and more general networks. Algorithms for these two cases are outlined and a number of applications are indicated.

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