Maximum and optimal 1-2 matching problem of the different kind

Abstract

We discuss 1-2 matchings, which are matchings in bipartite graphs G = (S S′, E) where their elements are pairs of edges with common endpoints in S. An algorithm to find an optimal 1-2 matching is derived. We also discuss 1-2 matchings of the different kind, which are special kinds of 1-2 matchings. The maximum 1-2 matching problem of the different kind can be analyzed by using augmenting trails of the different kind that are analogues of augmenting paths in the usual matching problem. The optimal 1-2 matching problem of the different kind can be reduced to the minimum-cost flow problem.

Subject Classification:

• 05C70
• 90C27

Keywords:

• Maximum matching
• Optimal matching
• Augmenting trail