A similarity measure for graphs with low computational complexity
Research output: Contribution to journal › Article › Scientific › peer-review
|Number of pages||13|
|Journal||Applied Mathematics and Computation|
|Publication status||Published - 1 Nov 2006|
|Publication type||A1 Journal article-refereed|
We present and analyze an algorithm to measure the structural similarity of generalized trees, a new graph class which includes rooted trees. For this, we represent structural properties of graphs as strings and define the similarity of two graphs as optimal alignments of the corresponding property stings. We prove that the obtained graph similarity measures are so called Backward similarity measures. From this we find that the time complexity of our algorithm is polynomial and, hence, significantly better than the time complexity of classical graph similarity methods based on isomorphic relations.