Loading...
Please wait, while we are loading the content...
Similar Documents
Optimal Embedding of Complete Binary Trees into Lines and Grids (1991)
| Content Provider | CiteSeerX |
|---|---|
| Author | Heckmann, R. Klasing, R. Monien, B. Unger, W. |
| Description | We consider several graph embedding problems which have applications in parallel and distributed computing and which have been unsolved so far. Our major result is that the complete binary tree can be embedded into the square grid of the same size with almost optimal dilation (up to a very small factor). To achieve this, we first state an embedding of the complete binary tree into the line with optimal dilation. 1 Introduction Graph embedding problems have gained importance in different areas of computer science (for a survey, cf. [MS90], [Ro88]). E.g. in the field of interconnection networks for parallel computer architectures, graph embeddings can generally be used to model the simulation of network and algorithm structures on a different network. Several types of networks have been considered, like hypercubes, shuffle-exchange networks, X-trees, binary trees, grids and lines. We will take a look at the latter ones. The importance of the tree-like structures arises from their use as... In: Proc. 17th Int. Workshop on Graph-Theoretic Concepts in Comp. Sci. (WG'91), LNCS 570 |
| File Format | |
| Language | English |
| Publisher | Springer Verlag |
| Publisher Date | 1991-01-01 |
| Access Restriction | Open |
| Subject Keyword | Shuffle-exchange Network Optimal Dilation Square Grid Introduction Graph Parallel Computer Architecture Different Area Major Result Different Network Tree-like Structure Arises Computer Science Optimal Embedding Graph Embeddings Small Factor Binary Tree Interconnection Network Latter One Several Graph Complete Binary Tree Algorithm Structure Several Type Distributed Computing |
| Content Type | Text |
| Resource Type | Article |
