Abstract
An efficient algorithm for subgraph isomorphism is presented. It combines tree search with relaxation by using resolution. Bitwise parallelism, which is an important factor in speed, is achieved during the resolution process even though a sequential computer is used. The algorithm can be easily modified to apply to multi-relation labeled graphs, attributed graphs and some higher order structures such as arrangements.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 371-379 |
| Number of pages | 9 |
| Journal | Pattern Recognition |
| Volume | 13 |
| Issue number | 5 |
| DOIs | |
| State | Published - 1981 |
| Externally published | Yes |
Keywords
- Constraint set
- Feasibility
- Relaxation
- Resolution
- Subgraph isomorphism
- Tree search
ASJC Scopus subject areas
- Software
- Signal Processing
- Computer Vision and Pattern Recognition
- Artificial Intelligence
Cite this
A subgraph isomorphism algorithm using resolution. / Cheng, J. K.; Huang, Thomas S.
In: Pattern Recognition, Vol. 13, No. 5, 1981, p. 371-379.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - A subgraph isomorphism algorithm using resolution
AU - Cheng, J. K.
AU - Huang, Thomas S
PY - 1981
Y1 - 1981
N2 - An efficient algorithm for subgraph isomorphism is presented. It combines tree search with relaxation by using resolution. Bitwise parallelism, which is an important factor in speed, is achieved during the resolution process even though a sequential computer is used. The algorithm can be easily modified to apply to multi-relation labeled graphs, attributed graphs and some higher order structures such as arrangements.
AB - An efficient algorithm for subgraph isomorphism is presented. It combines tree search with relaxation by using resolution. Bitwise parallelism, which is an important factor in speed, is achieved during the resolution process even though a sequential computer is used. The algorithm can be easily modified to apply to multi-relation labeled graphs, attributed graphs and some higher order structures such as arrangements.
KW - Constraint set
KW - Feasibility
KW - Relaxation
KW - Resolution
KW - Subgraph isomorphism
KW - Tree search
UR - http://www.scopus.com/inward/record.url?scp=0019728260&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0019728260&partnerID=8YFLogxK
U2 - 10.1016/0031-3203(81)90093-5
DO - 10.1016/0031-3203(81)90093-5
M3 - Article
AN - SCOPUS:0019728260
VL - 13
SP - 371
EP - 379
JO - Pattern Recognition
JF - Pattern Recognition
SN - 0031-3203
IS - 5
ER -