UNSPECIFIED (2000) Dense edge-disjoint embedding of complete binary trees in interconnection networks. In: 9th Australasian Workshop on Combinatorial Algorithms (AWOCA 98), SCH COMP CURTIN UNIV TECHNOL, PERTH, AUSTRALIA, JUL 27-30, 1998. Published in: THEORETICAL COMPUTER SCIENCE, 249 (2). pp. 325-342.

Full text not available from this repository.

Abstract

We describe dense edge-disjoint embeddings of the complete binary tree with n leaves in the following n-node communication networks: the hypercube, the de Bruijn and shuffle-exchange networks and the two-dimensional mesh. For the mesh and the shuffle-exchange graphs each edge is regarded as two parallel (or anti-parallel) edges. The embeddings have the following properties: paths of the tree are mapped onto edge-disjoint paths of the host graph and at most two tree nodes (just one of which is a leaf) are mapped onto each host node. We prove that the maximum distance from a leaf to the root of the tree is asymptotically as short as possible in all host graphs except in the case of the shuffle-exchange, in which case we conjecture that it is as short as possible. The embeddings facilitate efficient implementation of many P-RAM algorithms on these networks. (C) 2000 Elsevier Science B.V. All rights reserved.

Item Type:	Conference Item (UNSPECIFIED)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Journal or Publication Title:	THEORETICAL COMPUTER SCIENCE
Publisher:	ELSEVIER SCIENCE BV
ISSN:	0304-3975
Date:	28 October 2000
Volume:	249
Number:	2
Number of Pages:	18
Page Range:	pp. 325-342
Publication Status:	Published
Title of Event:	9th Australasian Workshop on Combinatorial Algorithms (AWOCA 98)
Location of Event:	SCH COMP CURTIN UNIV TECHNOL, PERTH, AUSTRALIA
Date(s) of Event:	JUL 27-30, 1998
URI:	http://wrap.warwick.ac.uk/id/eprint/12840

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item