@inproceedings{3e1f1736b76e4bb59581c8fc1a008ec9,

title = "The approximate graph matching problem",

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 problem (AGM): Given a pattern graph P and a data graph D, what is the distance between P and D ? 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.",

author = "Wang, {Jason T.L.} and Kaizhong Zhang and Chirn, {Gung Wei}",

note = "Funding Information: *This work wag supported in part by the National Science Foundation under Grants IRI-9224601 and IRI-9224602, by the New Jersey Institute of Technology under Grant No. 421280, by the Natural Sciences and Engineering Research Council of Canada under Grant No. OGP0046373, and by a grant from the AT&T Foundation. Publisher Copyright: {\textcopyright} 1994 Institute of Electrical and Electronics Engineers Inc.. All rights reserved.; 12th IAPR International Conference on Pattern Recognition - Conference B: Pattern Recognition and Neural Networks, ICPR 1994 ; Conference date: 09-10-1994 Through 13-10-1994",

year = "1994",

language = "English (US)",

series = "Proceedings - International Conference on Pattern Recognition",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "284--288",

booktitle = "Proceedings of the 12th IAPR International Conference on Pattern Recognition - Conference B",

address = "United States",

}