UNSPECIFIED (1993) DENSE EDGE-DISJOINT EMBEDDING OF COMPLETE BINARY-TREES IN THE HYPERCUBE. INFORMATION PROCESSING LETTERS, 45 (6). pp. 321-325. ISSN 0020-0190

Full text not available from this repository.

Abstract

We show that the complete binary tree with n > 8 leaves can be embedded in the hypercube with n nodes such that: paths of the tree are mapped onto edge-disjoint paths of the hypercube, at most two tree nodes (one of which is a leaf) are mapped onto each hypercube node, and the maximum distance from a leaf to the root of the tree is log2n + 1 hypercube edges (which is optimally short). This embedding facilitates efficient implementation of many P-RAM algorithms on the hypercube.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Journal or Publication Title:	INFORMATION PROCESSING LETTERS
Publisher:	ELSEVIER SCIENCE BV
ISSN:	0020-0190
Date:	16 April 1993
Volume:	45
Number:	6
Number of Pages:	5
Page Range:	pp. 321-325
Publication Status:	Published
URI:	http://wrap.warwick.ac.uk/id/eprint/21389

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item