A similarity measure for graphs with low computational complexity

M. Dehmer, Frank Emmert-Streib, J. Kilian

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)


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. (c) 2006 Elsevier Inc. All rights reserved.
Original languageEnglish
Pages (from-to)447-459
Number of pages13
JournalApplied Mathematics and Computation
Issue number1
Publication statusPublished - 01 Nov 2006

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics
  • Numerical Analysis


Dive into the research topics of 'A similarity measure for graphs with low computational complexity'. Together they form a unique fingerprint.

Cite this