A similarity measure for graphs with low computational complexity (Q861127)

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.