Subgraph Error-Correcting Isomorphisms for Syntactic Pattern Recognition

Wen-Hsiang Tsai; King Sun Fu

doi:10.1109/TSMC.1983.6313029

Subgraph Error-Correcting Isomorphisms for Syntactic Pattern Recognition

Wen-Hsiang Tsai , King Sun Fu

Department of Computer Science

Research output: Contribution to journal › Article › peer-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 language	American English
Pages (from-to)	48-62
Number of pages	15
Journal	IEEE Transactions on Systems, Man and Cybernetics
Volume	SMC-13
Issue number	1
DOIs	https://doi.org/10.1109/TSMC.1983.6313029
State	Published - Feb 1983

Access to Document

10.1109/TSMC.1983.6313029

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

Cite this

@article{23c72191983249388cbf235ad634f0db,

title = "Subgraph Error-Correcting Isomorphisms for Syntactic Pattern Recognition",

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.",

author = "Wen-Hsiang Tsai and Fu, {King Sun}",

year = "1983",

month = feb,

doi = "10.1109/TSMC.1983.6313029",

language = "American English",

volume = "SMC-13",

pages = "48--62",

journal = "IEEE Transactions on Systems, Man and Cybernetics",

issn = "0018-9472",

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

number = "1",

}

TY - JOUR

T1 - Subgraph Error-Correcting Isomorphisms for Syntactic Pattern Recognition

AU - Tsai , Wen-Hsiang

AU - Fu, King Sun

PY - 1983/2

Y1 - 1983/2

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 -

Subgraph Error-Correcting Isomorphisms for Syntactic Pattern Recognition

Abstract

Access to Document

Other files and links

Cite this