关键词: 匹配问题 组合优化算法 图匹配

Abstract:

For the matching problem of general graphs, the Edmonds algorithm is usually used. When the breadth-first search algorithm is used to find an augmenti  ng-path,a ＂flower＂ may be produced. In order to solve this problem, we can cut short the ＂flower＂ into a point, and keep on searching, then the obta
  ained graph after finding the augmenting-path is rehabilitated. The time efficiency of the algorithm is O（n^4） since the graph is cut short and rehabi  ilitated. However, when using the Gabow algorithm to find the augmenting-path, we should assign a fixed serial number to node and edges, and use differe nt arrays and pseudo node, thus we need not to deal with the ＂flower＂, and the time efficiency of this algorithm is O（nS）, but the space efficiency   of the algorithm is reduced. This paper proposes a depth-first search algorithm, and it is shown that using the proposed algorithm, the ＂flowers＂ wil   ll not appear when searching an augmenting-path. Moreover, the time effi- ciency is increased to O（n ＊ degree（n））, where degree（n） denotes the av   verage degree of nodes. In addition, when either ap- pending or deleting the edges in the graph, maximum matching can be computed quickly. It should be     pointed out that if we follow this idea to consider the breadth-first search, the order of magnitude is identical to the one in depth-first search.

Key words: matching problem, combinatorial optimization algorithm, graph matching