The Independent Spanning Trees of Torus
| Autor: | Bo-yen Lin, 林伯岩 |
|---|---|
| Rok vydání: | 2002 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 90 The study on independent spanning trees finds applications in fault-tolerant protocols for distributed computing networks. For example, the broadcasting in a network is sending a message from a given node to all other nodes in the network. We can design a fault-tolerant broadcasting scheme based on independent spanning trees [2] [8]. The fault-tolerance can be achieved by sending k copies of the message along k independent spanning trees rooted at the source node. If the source node is faultless, this scheme can tolerate up to k-1 faulty nodes. Two-dimension tori (or torus networks) are important due to its simple structure and suitability for developing algorithms. We are going to apply two-dimension tori in independent spanning tree for fault-torlerance-scheme. Obokata et al. have mentioned that an n-dimension torus is a 2n-channel graph and has 2n independent spanning trees rooted at any vertex. They view a 2-dimension torus R(r,c) as the product graph of cycles Cr and Cc, and construct four independent spanning trees of R(r,c) from independent spanning trees (paths) of Cr and Cc. Actually, their algorithm is a “cure-all”, and hence very hard to figure out. In this paper, we shall propose a simpler algorithm to construct four independent spanning trees on a two-dimension torus. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|