Optimal Dynamic Embedding of Trees into Arrays.

Abstract

An optimal method for dynamically embedding trees into arrays is presented. Every multihead tree machine of time complexity t(n) can be simulated on-line by a multihead d-dimensional machine in time 0(t(n)1+1/d/log t(n)). An information-theoretic argument gives the worst-case lower bound omega(t(n)1+1/d/log t(n)) on the time required. (Author)

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1981
Accession Number
ADA124489

Entities

People

  • Michael C. Loui

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Embedding

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Materials Science.
  • Parallel and Distributed Computing.