Augmenting trail theorem for the maximum 1-2 matching problem
Hiroki Izumi, Sennosuke Watanabe, Yoshihide Watanabe · Discrete Mathematics Algorithms and Applications · 2017
We consider the maximum 1-2 matching problem in bipartite graphs. The notion of the augmenting trail for the 1-2 matching problem, which is the extension of the notion of the augmenting path for the 1-1 matching problem is introduced. The main purpose of the present paper is to prove “the augmenting trail theorem” for the 1-2 matching problem in the bipartite graph, which is an analogue of the augmenting path theorem by Bergé for the usual 1-1 matching problems.