標題: | Wide diameters of de Bruijn graphs |
作者: | Kuo, Jyhmin Fu, Hung-Lin 應用數學系 Department of Applied Mathematics |
關鍵字: | de Bruijn;internally disjoint path;wide diameter |
公開日期: | 1-十月-2007 |
摘要: | The wide diameter of a graph is an important parameter to measure fault-tolerance of interconnection network. This paper proves that for any two vertices in de Bruijn undirected graph UB(d,n), there are 2d-2 internally disjoint paths of length at most 2n+1. Therefore, the (2d-2)-wide diameter of UB(d,n) is not greater than 2n+1. |
URI: | http://dx.doi.org/10.1007/s10878-007-9066-4 http://hdl.handle.net/11536/3996 |
ISSN: | 1382-6905 |
DOI: | 10.1007/s10878-007-9066-4 |
期刊: | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Volume: | 14 |
Issue: | 2-3 |
起始頁: | 143 |
結束頁: | 152 |
顯示於類別: | 會議論文 |