Narrow Results

This paper describes the computing alogrithms for the tree distance based on the structure preserving mapping. The distance is defined as the minimum sum of the weights of edit operations needed to transform tree T_α to tree T_β under restriction of the structure preserving mapping. The edit operations allow substituting a vertex of a tree to another, deleting a vertex of a tree and inserting a vertex to a tree. Proposed algorithms determine the distance between Tα and T_β in time O(N_αN_βL_α) or O(N_αN_βL_β), and in space O(N_αN_β), where N_α, N_β, L_α and L_β are the number of vertices of T_α, T_β, the number of’ leaves of T_α and T_β, respectively. The time complexity is close to the unapproachable lowest bound O(N_αN_β). Improved algorithms are presented. This tree distance can be applied to any problems including pattern recognition, syntactic tree comparison and classification, and tree comparison whose structures are important in structure preserving mapping.

In the previous paper on a tree-to-tree editing problem some errors were included. This letter describes the corrected definition of a structure preserving mapping between rooted and ordered trees and a computing method of the tree distance based on the mapping.

The scaling properties of the portal vein and the hepatic vein are examined, based on three-dimensional computed tomography images of casts of human livers. In particular, a quantitative analysis of the branching ratio based on the Strahler ordering scheme as well as the diameter and length ratios are performed. To quantify the segment anatomy of the liver, the volume of supplied liver parenchyma is measured and related to the corresponding vessel radius. The implications of these findings for segment-oriented liver surgery are discussed. We also investigate the 3D interdependence of the intertwined portal and hepatic veins based on a concept of tree distance that will be introduced.