Finding approximate patterns in undirected acyclic graphs
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 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.
distance metric graph matching pattern discovery website analysis chemical substructure search