A similarity measure for graphs with low computational complexity

DOI10.1016/j.amc.2006.04.006zbMath1111.05019OpenAlexW2166251704MaRDI QIDQ861127

Frank Emmert-Streib, Matthias Dehmer, Jürgen Kilian

Publication date: 9 January 2007

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2006.04.006

zbMATH Keywords

isomorphismgraph similaritygeneralized tree

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

A comparative analysis of the Tanimoto index and graph edit distance for measuring the topological similarity of trees ⋮ Similarity in languages and programs ⋮ The domination numbers of cylindrical grid graphs ⋮ Structure-based graph distance measures of high degree of precision ⋮ Fifty years of graph matching, network alignment and network comparison ⋮ A comparative analysis of multidimensional features of objects resembling sets of graphs ⋮ Structural similarity of directed universal hierarchical graphs: a low computational complexity approach ⋮ Comparing large-scale graphs based on quantum probability theory ⋮ Graph comparison via nonlinear quantum search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alignment of trees -- an alternative to tree edit
• On the editing distance between unordered labeled trees
• The tree-to-tree editing problem
• On a certain distance between isomorphism classes of graphs
• An Algorithm for Subgraph Isomorphism
• The Tree-to-Tree Correction Problem
• Algorithms on Strings, Trees and Sequences
• Inexact graph matching for structural pattern recognition