標題: Wide diameters of de Bruijn graphs
作者: Kuo, Jyhmin
Fu, Hung-Lin
應用數學系
Department of Applied Mathematics
關鍵字: de Bruijn;internally disjoint path;wide diameter
公開日期: 1-Oct-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
Appears in Collections:Conferences Paper