On the Height of Independent Spanning Trees in Chordal Rings
| Autor: | Jing Xian Lee, 李景賢 |
|---|---|
| Rok vydání: | 2001 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 89 Due to the innovation of information technology, the age of networking has come. The quality of a network depends on the topology of the network. The ring network that is easily implemented has become one of popular networks. The chordal ring with degree of 4 is a variation of ring network. By adding extra two links, the reliability and fault-tolerance of the network are enhanced. Furthermore the transmission delay of the network is reduced. A chordal ring, denoted by CR(N,d), is a graph G=(V,E) with V={0,1,…,N-1} and E={(u,v)|[v-u]N=1 or d}, where 2≦d＜N/2 and [r]N denotes r modulo N. Iwasaki et al. have proposed a linear time algorithm to find four independent spanning trees in a chordal ring. Thus for any two vertices in a chordal ring, four node disjoint paths can be determined immediately through this way. In this thesis, we shall propose two algorithms based on Iwasaki’s result. One algorithm is to determine the height of four independent spanning trees in constant time. The other algorithm is to make four minimum independent spanning trees and its time complexity is O(N2). |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|