Search

Various algorithms have been proposed for the problem of drawing rooted ordered trees. As one of them, Unno and colleagues [1] presented an O(n3) time algorithm that (1) produces an initial drawing of a given tree T, and then (2) finds a narrower drawing by repeatedly moving subtrees (n is the number of nodes in T). In this paper, we show that the same drawing can be obtained more efficiently by maintaining the contours of subtrees. If a natural restriction is imposed on the sizes of nodes, our method can be executed in a time O(n·α(n, n)), where α is a functional inverse of Ackermann's function. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(5): 31–41, 1997 [ABSTRACT FROM AUTHOR]

This paper discusses the problems of finding one of the largest similar substructures in tree Tb to tree Ta, where both Ta and Tb are rooted and ordered trees (RO-trees) or unrooted and cyclically ordered trees (CO-trees). A maximal closest common ancestor mapping and a largest similar substructure in Tb to Ta based on this mapping are defined and two algorithms are proposed for finding one of the largest similar substructures for RO-trees and that for CO-trees. The time and space complexities of the algorithm for RO-trees are OT(NaNb) and OS(NaNb), respectively; and those of the algorithm for CO-trees are OT(mambNaNb) and OS((ma + mb)NaNb), respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(2): 92–104, 1997 [ABSTRACT FROM AUTHOR]