A subgraph isomorphism algorithm using resolution

J. K. Cheng, T. S. Huang

Research output: Contribution to journalArticlepeer-review

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

Keywords

  • Constraint set
  • Feasibility
  • Relaxation
  • Resolution
  • Subgraph isomorphism
  • Tree search

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'A subgraph isomorphism algorithm using resolution'. Together they form a unique fingerprint.

Cite this