loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
An Eigendecomposition Approach to Weighted Graph Matching Problems
September 1988 (vol. 10 no. 5)
pp. 695-703
ASCII Text
x 
 
S. Umeyama, "An Eigendecomposition Approach to Weighted Graph Matching Problems," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, no. 5, pp. 695-703, September, 1988.
 
 
BibTex
x
 
@article{ 10.1109/34.6778,
author = {S. Umeyama},
title = {An Eigendecomposition Approach to Weighted Graph Matching Problems},
journal ={IEEE Transactions on Pattern Analysis and Machine Intelligence},
volume = {10},
number = {5},
issn = {0162-8828},
year = {1988},
pages = {695-703},
doi = {http://doi.ieeecomputersociety.org/10.1109/34.6778},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
TI - An Eigendecomposition Approach to Weighted Graph Matching Problems
IS - 5
SN - 0162-8828
SP695
EP703
EPD - 695-703
A1 - S. Umeyama,
PY - 1988
KW - pattern recognition; eigendecomposition; weighted graph matching; adjacency matrices; undirected-graph-matching; Hermitian matrices; directed-graph-matching; eigenvalues and eigenfunctions; graph theory; pattern recognition
VL - 10
JA - IEEE Transactions on Pattern Analysis and Machine Intelligence
ER -
 

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.

[1] W. H. Tsai and K. S. Fu, "Error-correcting isomorphisms of attributed relational graphs for pattern analysis,"IEEE Trans. Syst., Man, Cybernet., vol. SMC-9, pp. 757-768, Dec. 1979.
[2] H. S. Baird,Model-Based Image Matching Using Location, Cambridge, MA: MIT Press, 1986.
[3] M. You and A. K. C. Wong, "An algorithm for graph optimal isomorphism," inProc. 1984 ICPR, pp. 316-319, 1984.
[4] L. Kitchen and A. Rosenfeld, "Discrete relaxation for matching relational structures,"IEEE Trans. Syst., Man, Cybernet., vol. SMC-9, pp. 869-874, Dec. 1979.
[5] L. Kitchen, "Relaxation applied to matching quantitative relational structures,"IEEE Trans. Syst., Man, Cybernet., vol. SMC-10, pp. 96-101, Feb. 1980.
[6] M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.
[7] D. Dubois and H. Prade,Fuzzy Sets and Systems: Theory and Applications. New York: Academic, 1980.
[8] A. J. Hoffman and H. W. Wielandt, "The variation of the spectrum of a normal matrix,"Duke Math. J., vol. 20, pp. 37-39, 1953.
[9] C. H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, NJ: Prentice-Hall, 1982.

Index Terms:
pattern recognition; eigendecomposition; weighted graph matching; adjacency matrices; undirected-graph-matching; Hermitian matrices; directed-graph-matching; eigenvalues and eigenfunctions; graph theory; pattern recognition
Citation:
S. Umeyama, "An Eigendecomposition Approach to Weighted Graph Matching Problems," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, no. 5, pp. 695-703, Sept. 1988, doi:10.1109/34.6778
Usage of this product signifies your acceptance of the Terms of Use.