Name
Abstract | ||
|---|---|---|
In this paper, Umeyama's eigen-decomposition approach to weighted graph matching problems is critically examined. We argue that Umeyama's approach only guarantees to work well for graphs that satisfy three critical conditions: (1) The pair of weighted graphs to be matched must be nearly isomorphic; (2) The eigenvalues of the adjacency matrix of each graph have to be single and isolated enough to each other; (3) The rows of the matrix of the corresponding absolute eigenvetors cannot be very similar to each other. For the purpose of matching general weighted graph pairs without such imposed constraints, we shall propose an approximate formula with a theoretical guarantee of accuracy, from which Umeyama's formula can be deduced as a special case. Based on this approximate formula, a new algorithm for matching weighted graphs is developed. The experimental results demonstrate great improvements to the accuracy of weighted graph matching. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74171-8_131 | ICIC (1) |
Keywords | Field | DocType |
weighted graph,general weighted graph pair,weighted graph matching,eigen-decomposition method,critical condition,approximate formula,corresponding absolute eigenvetors,eigen-decomposition approach,adjacency matrix,great improvement,decomposition method,satisfiability,pattern recognition,graph matching | Adjacency matrix,Discrete mathematics,Combinatorics,Comparability graph,Graph energy,Line graph,Directed graph,Matching (graph theory),Factor-critical graph,3-dimensional matching,Mathematics | Conference |
Volume | ISSN | ISBN |
4681 | 0302-9743 | 3-540-74170-4 |
Citations | PageRank | References |
7 | 0.52 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guoxing Zhao | 1 | 16 | 3.43 |
| Bin Luo | 2 | 802 | 107.57 |
| Jin Tang | 3 | 322 | 62.02 |
| Jinxin Ma | 4 | 22 | 6.02 |