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 language | English (US) |
---|---|
Pages (from-to) | 473-483 |
Number of pages | 11 |
Journal | Pattern Recognition |
Volume | 35 |
Issue number | 2 |
DOIs | |
State | Published - Feb 2002 |
All Science Journal Classification (ASJC) codes
- Software
- Signal Processing
- Computer Vision and Pattern Recognition
- Artificial Intelligence
Keywords
- Chemical substructure search
- Distance metric
- Graph matching
- Pattern discovery
- Website analysis