Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Dense edge-disjoint embedding of complete binary trees in interconnection networks

Tools
- Tools
+ Tools

Ravindran, Somasundaram, Gibbons, Alan (Alan M.) and Paterson, Michael S. (2000) Dense edge-disjoint embedding of complete binary trees in interconnection networks. Theoretical Computer Science, Volume 249 (Number 2). pp. 325-342.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Official URL: http://dx.doi.org/10.1016/S0304-3975(00)00066-9

Request Changes to record.

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.

Item Type: Journal Item
Subjects: Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Journal or Publication Title: Theoretical Computer Science
Publisher: Elsevier Science BV
ISSN: 0304-3975
Official Date: 28 October 2000
Dates:
DateEvent
28 October 2000Published
Volume: Volume 249
Number: Number 2
Number of Pages: 18
Page Range: pp. 325-342
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Version or Related Resource: Ravindrana, S., Gibbons, A.M. and Paterson, M.S. (1995). Dense edge-disjoint embedding of complete binary trees in interconnection networks. University of Warwick. Department of Computer Science. (Department of Computer Science research report, 284).
Title of Event: 9th Australasian Workshop on Combinatorial Algorithms (AWOCA 98)
Location of Event: Perth, Australia
Date(s) of Event: 27-30 Jul 1998
Related URLs:
  • Related item in WRAP

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us