An optimal emulator and VLSI layout for complete binary trees
type: Item
instance of: scholarly article
title: An optimal emulator and VLSI layout for complete binary trees
zbMATH Open document ID: 0865.68085
author: Nancy Eleser
author: Kemal Efe
published in: Acta Informatica
publication date: 1996-09-25T00:00:00Z
review text: How complex does a graph need to be in order to emulate an arbitrary size complete binary tree with the same level of efficiency as would be obtained by a directed complete graph? In this paper, this question is answered by showing that any \(N= 2^n\)-node graph needs to have at least \({{3N-2} \over 2}\) edges in order to perform this emulation. Subsequently, a graph is presented which meets this bound, and it is shown how to optimally embed an arbitrary size complete binary tree in the proposed graph. It is also shown how to optimally embed a \(kN\) node cycle in the proposed graph of \(N\) nodes with unit dilation, unit congestion and uniform load of \(k\). Finally optimal VLSI layouts are presented for the proposed graph which require asymptotically same area as the corresponding layouts for complete binary trees.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68W35
zbMATH DE Number: 918708
zbMATH Keywords: parallel architectures
zbMATH Keywords: VLSI layout
zbMATH Keywords: graph embedding
zbMATH Keywords: binary trees
MaRDI profile type: Publication
full work available at URL: s002360050093
OpenAlex ID: W1977119748
DOI: 10.1007/S002360050093
description: scientific article; zbMATH DE number 918708