THE RECOGNITION OF UNION TREES

Union trees are rooted trees formed in performing a sequence of disjoi nt-set union operations, where a union rule can be generally described by a function f. In this paper, a polynomial-time algorithm is presen ted that recognizes f-union trees for any polynomial-time computable m onotone function f. Furthermore, a linear-time implementation of the a lgorithm is given for linear and monotone functions, which includes th e two well-known functions - size and rank.