Constant-Time Tree algorithms on Reconfigurable Meshes on Size n x n.
Journal
J. Parallel Distrib. Comput.
Journal Volume
26
Journal Issue
2
Pages
137-150
Date Issued
1995
Author(s)
Abstract
Recently, an elegant and powerful architecture called the reconfigurable mesh has been proposed in the literature. In essence, a reconfigurable mesh consists of a mesh-connected architecture enhanced by the addition of a dynamic bus system whose configuration changes in response to computational and communication needs. In this paper we show that the reconfigurable mesh architecture can be exploited to yield very simple constant-time algorithms to solve a number of important computational problems involving trees. Specifically, we address the problem of generating the computation tree form of an arithmetic expression, the problem of reconstructing a binary tree from its preorder and inorder traversals, and the problem of reconstructing an ordered forest from its preorder and postorder traversals. We show that with an input of size n, all these problems find constant-time solutions on a reconfigurable mesh of size n × n. © 1995 Academic Press, Inc.
SDGs
Type
journal article