High-density optical interconnects within large-scale systems
Christoph Berger, Marcel A. Kossel, et al.
SPIE Photonics Fabrication Europe 2002
The problem of constructing the suffix tree of a tree is a generalization of the problem of constructing the suffix tree of a string. It has many applications, such as in minimizing the size of sequential transducers and in tree pattern matching. The best-known algorithm for this problem is Breslauer's O(n log |Σ|) time algorithm where n is the size of the CS-tree and |Σ| is the alphabet size, which requires O(n log n) time if |Σ| is large. We improve this bound by giving an optimal linear time algorithm for integer alphabets. We also describe a new data structure, the Bsuffix tree, which enables efficient query for patterns of completely balanced k-ary trees from a k-ary tree or forest. We also propose an optimal O(n) algorithm for constructing the Bsurffix tree for integer alphabets.
Christoph Berger, Marcel A. Kossel, et al.
SPIE Photonics Fabrication Europe 2002
D. Weller, G.R. Harp, et al.
SPIE OE/LASE 1994
D. Coppersmith, Fred Mintzer, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering