Weighted Graph Matching Algorithms Using Eigen-Decomposition Approach
Summary :
This paper discusses the approximate solution to the weighted graph matching problem (WGMP) both for undirected and directed graphs. WGMP is the problem of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method employs an analytic approach using the eigen-decomposition of the adjacency matrix (in the case of undirected matching problem) or the singular value decomposition of the incidence matrix (in the case of directed graph matching problem) of a given graph. A technique for reducing the execution time to search for the solution is given. Simulation experiments are also given to evaluate the performance of the proposed method.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E70-E No.9 pp.809-816
- Publication Date
- 1987/09/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shinji UMEYAMA, "Weighted Graph Matching Algorithms Using Eigen-Decomposition Approach" in IEICE TRANSACTIONS on transactions,
vol. E70-E, no. 9, pp. 809-816, September 1987, doi: .
Abstract: This paper discusses the approximate solution to the weighted graph matching problem (WGMP) both for undirected and directed graphs. WGMP is the problem of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method employs an analytic approach using the eigen-decomposition of the adjacency matrix (in the case of undirected matching problem) or the singular value decomposition of the incidence matrix (in the case of directed graph matching problem) of a given graph. A technique for reducing the execution time to search for the solution is given. Simulation experiments are also given to evaluate the performance of the proposed method.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e70-e_9_809/_p
Copy
@ARTICLE{e70-e_9_809,
author={Shinji UMEYAMA, },
journal={IEICE TRANSACTIONS on transactions},
title={Weighted Graph Matching Algorithms Using Eigen-Decomposition Approach},
year={1987},
volume={E70-E},
number={9},
pages={809-816},
abstract={This paper discusses the approximate solution to the weighted graph matching problem (WGMP) both for undirected and directed graphs. WGMP is the problem of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method employs an analytic approach using the eigen-decomposition of the adjacency matrix (in the case of undirected matching problem) or the singular value decomposition of the incidence matrix (in the case of directed graph matching problem) of a given graph. A technique for reducing the execution time to search for the solution is given. Simulation experiments are also given to evaluate the performance of the proposed method.},
keywords={},
doi={},
ISSN={},
month={September},}
Copy
TY - JOUR
TI - Weighted Graph Matching Algorithms Using Eigen-Decomposition Approach
T2 - IEICE TRANSACTIONS on transactions
SP - 809
EP - 816
AU - Shinji UMEYAMA
PY - 1987
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E70-E
IS - 9
JA - IEICE TRANSACTIONS on transactions
Y1 - September 1987
AB - This paper discusses the approximate solution to the weighted graph matching problem (WGMP) both for undirected and directed graphs. WGMP is the problem of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method employs an analytic approach using the eigen-decomposition of the adjacency matrix (in the case of undirected matching problem) or the singular value decomposition of the incidence matrix (in the case of directed graph matching problem) of a given graph. A technique for reducing the execution time to search for the solution is given. Simulation experiments are also given to evaluate the performance of the proposed method.
ER -
English
