Computing on a Free Tree via Complexity-Preserving Mappings

It appears that in a number of cases computing over free trees is no more difficult than computing over linear lists. In the arithmetic model, we have established a strict equivalence between the interval query problem and its generalization on a tree structure. In the reference machine model, the concept of efficiency is traditionally captured by the class of retrieval problems which can be solved in O(nP0LY LOG(n)) space and O(POLYLOG(n)) time. We have shown that in a number of examples this class is closed under transformations from lists to trees. Characterizing the set of problems and techniques for which this holds is an interesting open problem.

Authors

• Bernard Chazelle

Keywords

• Tree graphs
• Mathematical model
• Arithmetic
• Communication networks
• Tree Segmentation
• Data Structure
• Remainder Of This Section
• Subtree
• Tree Size