Tampere University of Technology

TUTCRIS Research Portal

A similarity measure for graphs with low computational complexity

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Pages (from-to)447-459
Number of pages13
JournalApplied Mathematics and Computation
Volume182
Issue number1
DOIs
Publication statusPublished - 1 Nov 2006
Externally publishedYes
Publication typeA1 Journal article-refereed

Abstract

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.

Keywords

  • Computational complexity, Dynamic programming, Graph similarity, Graph theory