An eigendecomposition approach to weighted graph matching problems
- 1 September 1988
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 10 (5) , 695-703
- https://doi.org/10.1109/34.6778
Abstract
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.<>Keywords
This publication has 2 references indexed in Scilit:
- THE VARIATION OF THE SPECTRUM OF A NORMAL MATRIXPublished by World Scientific Pub Co Pte Ltd ,2003
- Error-Correcting Isomorphisms of Attributed Relational Graphs for Pattern AnalysisIEEE Transactions on Systems, Man, and Cybernetics, 1979