Optimal dynamic embedding of X-trees into arrays

DOI10.1016/0304-3975(88)90144-2MaRDI QIDQ1105377zbMATH OpenOpenAlexFDO

Authors A. Scottedward Hodel, Michael C. Loui

Publication date 1988

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(88)90144-2

zbMATH Keywords

arraydynamic embeddingmultihead bounded activity machineon-line simulationstorage mediumX-tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

We present a dynamic embedding of the contents of a storage medium organized as an X-tree into a storage medium organized as a d-dimensional array. Let X be a multihead bounded activity machine with a single storage tape organized as an X-tree. A multihead bounded activity machine D with a single tape organized as a d-dimensional array is used to simulate X on-line. If X runs in time t(n) on inputs of length n, then D simulates X in time \(O(t(n)^{1+1/d}/\log t(n))\). Furthermore, this simulation is optimal.

Recommendations

• Optimal simulation of tree arrays by linear arrays
• Efficient Dynamic Embeddings of Binary Trees into Hypercubes
• EFFICIENT EMULATIONS FOR X-TREES AND /w-ARY TREES*
• Efficient Embeddings of Trees in Hypercubes
• Optimal dynamic embeddings of complete binary trees into hypercubes

Cites work

• A fast implementation of a multidimensional storage into a tree storage
• Cost Trade-offs in Graph Embeddings, with Applications
• Graphs That are Almost Binary Trees
• On the Minimum Computation Time of Functions
• Optimal Dynamic Embedding of Trees into Arrays
• Relations Among Complexity Measures
• Simulations among multidimensional Turing machines
• Space and Time Hierarchies for Classes of Control Structures and Data Structures
• Space-Time Trade-Offs in Structured Programming

Cited in

(1)

• Optimal simulation of tree arrays by linear arrays

This page was built for publication: Optimal dynamic embedding of X-trees into arrays

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105377)