AN EIGENDECOMPOSITION APPROACH TO WEIGHTED GRAPH MATCHING PROBLEMS
AN EIGENDECOMPOSITION APPROACH TO WEIGHTED GRAPH MATCHING PROBLEMS
复制标题
DOI：
10.1109/34.6778
复制
发表时间：
1988-09-01
影响因子：
23.6
通讯作者：
UMEYAMA, S
中科院分区：
文献类型：
--
作者：
UMEYAMA, S
讨论了无向图和有向图的加权图匹配问题的近似解。赋权图匹配问题是在两个赋权图之间寻找最优匹配的问题，这两个赋权图是在每条弧处都有权的图。该方法使用解析方法而不是组合或迭代方法来解决最优匹配问题。利用邻接矩阵的特征分解(在无向图匹配问题中)或由邻接矩阵得到的厄米特矩阵(在有向图匹配问题中)，当图彼此足够接近时，可以有效地找到接近最优的匹配。给出了仿真结果，评价了该方法的性能。
An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs. The weighted-graph-matching problem is that of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method uses an analytic instead of a combinatorial or iterative approach to the optimum matching problem. Using the eigendecompositions of the adjacency matrices (in the case of the undirected-graph-matching problem) or Hermitian matrices derived from the adjacency matrices (in the case of the directed-graph-matching problem), a matching close to the optimum can be found efficiently when the graphs are sufficiently close to each other. Simulation results are given to evaluate the performance of the proposed method.<>