Nordic Journal of Computing Bibliography

Owen Kaser. Optimal Height Reduction Problems for Tree-Structured Hierarchies. Nordic Journal of Computing, 4(4):357-379, Winter 1997.
Abstract

Hierarchical 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


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database