THE SUBTREE MAX GAP PROBLEM WITH APPLICATION TO PARALLEL STRING COVERING

We introduce the subtree max gap problem. Consider a rooted tree T wit h n leaves whose internal nodes have at least two children. Each leaf is associated with a real number. For each internal node v, let A(v) b e the set of numbers associated with the leaves in the subtree rooted at v which are regarded as points on the x-axis. The subtree max gap p roblem is to compute the maximum distance (gap) between any two consec utive points of A(v) for every internal node v of T. Our algorithm for the subtree max gap problem follows a series of reductions to other c ombinatorial problems which are interesting on their own merit. The al gorithm runs in O(log n) time using n processors on the concurrent-rea d exclusive-write parallel random access machine. The subtree max gap problem plays a central role in the parallel solution of the string co vering problem. Recently, Iliopoulos, at al. (1993, in ''Proc. 26th Sy mposium in Theory of Computing,'' pp. 290-299) gave an O(n log n) time sequential algorithm for the string covering problem. Neither paralle lizing the above sequential algorithm nor using known techniques from algorithms on strings seems to yield an efficient parallel algorithm f or string covering. Our parallel algorithm thus follows a new approach , suing suffix trees and reducing the string covering problem to the s ubtree max gap problem. The algorithm runs in O(log n) time using n pr ocessors on the concurrent-read concurrent-write parallel random acces s machine, thereby matching the number of operations in Iliopoulos. at al. (C) 1995 Academic Press, Inc.