TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

A similarity measure for graphs with low computational complexity

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivut447-459
Sivumäärä13
JulkaisuApplied Mathematics and Computation
Vuosikerta182
Numero1
DOI - pysyväislinkit
TilaJulkaistu - 1 marraskuuta 2006
Julkaistu ulkoisestiKyllä
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.