A similarity measure for graphs with low computational complexity
type: Item
instance of: scholarly article
title: A similarity measure for graphs with low computational complexity
zbMATH Open document ID: 1111.05019
author: Matthias Dehmer
author: Frank Emmert-Streib
author: Jürgen Kilian
published in: Applied Mathematics and Computation
publication date: 2007-01-09T00:00:00Z
review text: A class of generalized trees is defined that includes directed, rooted trees. Using this class, a measure of structural similarity based on optimal alignment of property strings of these graphs is developed, and an efficient dynamic programming strategy is given. In this way, similarity measures using isomorphism of tree structures are extended to the richer class of generalized trees while maintaining efficient computation.
reviewed by: Charles J. Colbourn
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 5083699
zbMATH Keywords: graph similarity
zbMATH Keywords: generalized tree
zbMATH Keywords: isomorphism
MaRDI profile type: Publication
full work available at URL: j.amc.2006.04.006
OpenAlex ID: W2166251704
cites work: Q3241581
cites work: Inexact graph matching for structural pattern recognition
cites work: Algorithms on Strings, Trees and Sequences
cites work: Alignment of trees -- an alternative to tree edit
cites work: Q3309883
cites work: Q3960888
cites work: Q5528329
cites work: The tree-to-tree editing problem
cites work: Q3960889
cites work: Q3778584
cites work: The Tree-to-Tree Correction Problem
cites work: An Algorithm for Subgraph Isomorphism
cites work: On a certain distance between isomorphism classes of graphs
cites work: On the editing distance between unordered labeled trees
DOI: 10.1016/J.AMC.2006.04.006
description: scientific article; zbMATH DE number 5083699