The approximate graph matching problem
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 284-288
- https://doi.org/10.1109/icpr.1994.576921
Abstract
Labeled graphs are graphs in which each node and edge has a label. The distance between two labeled graphs is considered to be the weighted sum of the costs of edit operations (insert, delete and relabel the nodes and edges) to transform one graph to the other. The paper considers two variants of the approximate graph matching (AGM) problem: given a pattern graph P and a data graph D, what is the distance between P and D? and what is the minimum distance between P and D when subgraphs can be freely removed from D? We show that no efficient algorithm can solve either variant of the AGM, unless P=NP. We then give a polynomial-time approximation algorithm to solve this problem.Keywords
This publication has 5 references indexed in Scilit:
- Exact and approximate algorithms for unordered tree matchingIEEE Transactions on Systems, Man, and Cybernetics, 1994
- On the editing distance between unordered labeled treesInformation Processing Letters, 1992
- Use of techniques derived from graph theory to compare secondary structure motifs in proteinsJournal of Molecular Biology, 1990
- Computational approaches to discovering semantics in molecular biologyProceedings of the IEEE, 1989
- Data Structures and Network AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1983