TY - JOUR
T1 - Subgraph Error-Correcting Isomorphisms for Syntactic Pattern Recognition
AU - Tsai , Wen-Hsiang
AU - Fu, King Sun
PY - 1983/1/1
Y1 - 1983/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0020497981&partnerID=8YFLogxK
U2 - 10.1109/TSMC.1983.6313029
DO - 10.1109/TSMC.1983.6313029
M3 - Article
AN - SCOPUS:0020497981
VL - SMC-13
SP - 48
EP - 62
JO - IEEE Transactions on Systems, Man and Cybernetics
JF - IEEE Transactions on Systems, Man and Cybernetics
SN - 0018-9472
IS - 1
ER -