Subgraph Error-Correcting Isomorphisms for Syntactic Pattern Recognition

Wen-Hsiang Tsai , King Sun Fu

Research output: Contribution to journalArticlepeer-review

84 Scopus citations

Abstract

The structure-preserved error-correcting graph isomorphism proposed by Tsai and Fu [1] for matching patterns represented by attributed relational graphs is extended to the case of subgraphs. The resulting subgraph error-correcting isomorphism, which includes the structure-preserved error-correcting graph isomorphism as a special case, is useful for recognizing partially viewed or structurally distorted patterns. After formulating a subgraph error-correcting isomorphism as a state-space tree-search problem, heuristic information useful for speeding up the search is suggested and an ordered-search algorithm is proposed for finding an optimal subgraph error-correcting isomorphism.

Original languageEnglish
Pages (from-to)48-62
Number of pages15
JournalIEEE Transactions on Systems, Man and Cybernetics
VolumeSMC-13
Issue number1
DOIs
StatePublished - 1 Jan 1983

Fingerprint Dive into the research topics of 'Subgraph Error-Correcting Isomorphisms for Syntactic Pattern Recognition'. Together they form a unique fingerprint.

Cite this