Graph matching is a NP-Hard problem. In this paper, we relax the admissible set of permutation matrices and meantime incorporate a barrier function into the objective function. The resulted model is equivalent to the original model. Alternate iteration algorithm is designed to solve it. It is proven that the algorithm proposed is locally convergent. Our experimental results reveal that the proposed algorithm outperforms the algorithm in .

Weighted graph matching is computationally challenging due to the combinatorial nature of the set of permutations. In this paper, a new relaxation approach to weighted graph matching is proposed, by which a new matching algorithm, named alternate iteration algorithm, is designed. It is proved that the algorithm proposed is locally convergent. Experiments are presented to show the effectiveness of the proposed algorithm.