AbstractHierarchical descriptions of objects may be restructured by selective inlining. This paper considers the improvement of tree-structured hierarchies. Trade-offs are observed between the increased size of an inlined description, and its reduced number of hierarchical levels. Optimization problems are formulated where the minimum size expansion is incurred while obtaining a desired height reduction. Two varieties of inlining are considered, and weighted graphs are used to model the optimization problem. For one variety of inlining, an O(n sqrt(H log n))-time algorithm is described; it can reduce an n-cell hierarchy to H levels, if the structure of the hierarchy is linear. For general trees, an O(H n2)-time algorithm is given. With the other variety of inlining, the linear problem is solved in O(H2 n3) time, while for general trees with certain arc-weight constraints, a 2-approximate algorithm runs in O(H n2) time. Related open problems are given and applications are discussed.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Additional Key Words and Phrases: hierarchy, restructuring, inlining, optimization, graphs, trees, algorithms
Selected references
- Greg N. Frederickson. Optimal algorithms for tree partitioning. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 168-177, San Francisco, California, 28-30 January 1991.
- D. S. Hirschberg and L. L. Larmore. The least weight subsequence problem. SIAM Journal on Computing, 16(4):628-638, August 1987.
- Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, October 1983.
- Robert Wilber. The concave least-weight subsequence problem revisited. Journal of Algorithms, 9(3):418-425, September 1988.