A subgraph isomorphism algorithm using resolution

J. K. Cheng, Thomas S Huang

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)371-379
Number of pages9
JournalPattern Recognition
Volume13
Issue number5
DOIs
StatePublished - 1981
Externally publishedYes

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 journalArticle

Cheng, J. K. ; Huang, Thomas S. / A subgraph isomorphism algorithm using resolution. In: Pattern Recognition. 1981 ; Vol. 13, No. 5. pp. 371-379.
@article{d92d552400184c5a9d3013b98d83dcc9,
title = "A subgraph isomorphism algorithm using resolution",
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.",
keywords = "Constraint set, Feasibility, Relaxation, Resolution, Subgraph isomorphism, Tree search",
author = "Cheng, {J. K.} and Huang, {Thomas S}",
year = "1981",
doi = "10.1016/0031-3203(81)90093-5",
language = "English (US)",
volume = "13",
pages = "371--379",
journal = "Pattern Recognition",
issn = "0031-3203",
publisher = "Elsevier Limited",
number = "5",

}

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 -