Proposes a distance measure between unrooted and unordered trees based on the strongly structure-preserving mapping (SSPM). SSPM can make correspondences between the vertices of similar substructures of given structures more strictly than previously proposed mappings. The time complexity of computing the distance between trees T/sub a/ and T/sub b/ is O(m/sub bsup 3/N/sub a/N/sub b/), where N/sub a/ and N/sub b/ are the number of vertices in trees T/sub a/ and T/sub b/, respectively; m/sub a/ and m/sub b/ are the maximum degrees of a vertex in T/sub a/ and T/sub b/, respectively; and m/sub aspl les/m/sub b/ is assumed. The space complexity of the method is O(N/sub a/N/sub b/).
展开▼
机译：提出了一种基于强结构保留映射（SSPM）的无根树与无序树之间的距离度量。与先前提出的映射相比，SSPM可以更严格地使给定结构的相似子结构的顶点之间的对应关系。计算树T / sub a /和T / sub b /之间的距离的时间复杂度为O（m / sub bsup 3 / N / sub a / N / sub b /），其中N / sub a /和N / sub b /分别是树T / sub a /和T / sub b /中的顶点数； m / sub a /和m / sub b /分别是T / sub a /和T / sub b /中顶点的最大度数；并且假设m / sub aspl les / m / sub b /。该方法的空间复杂度为O（N / sub a / N / sub b /）。
展开▼
