Finding approximate patterns in undirected acyclic graphs

Jason T.L. Wang, Kaizhong Zhang, George Chang, Dennis Shasha

Research output: Contribution to journalArticlepeer-review

Abstract

We consider an approximate pattern matching problem for undirected acyclic graphs. Specifically, let P be a pattern graph, D a data graph and t an integer. We present an algorithm to locate a subgraph in D whose distance from P is at most t. The distance measure used here is the degree-2 metric published previously. The time complexity of our algorithm is O(NpNDd √d log d) where Np and ND are the number of nodes in P and D, respectively; d = min dP,dD; dp and dD are the maximum degree of P and D, respectively. Central to our algorithm is a procedure for finding approximate patterns in rooted unordered trees and freely allowing cuts. We discuss two applications of the algorithms in chemical information search and website management on the Internet.

Original languageEnglish (US)
Pages (from-to)473-483
Number of pages11
JournalPattern Recognition
Volume35
Issue number2
DOIs
StatePublished - Feb 2002

Keywords

  • Chemical substructure search
  • Distance metric
  • Graph matching
  • Pattern discovery
  • Website analysis

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Finding approximate patterns in undirected acyclic graphs'. Together they form a unique fingerprint.

Cite this