| 扩展de Bruijn图的生成树和广播 |
| |
| 引用本文： | 高随祥,杨德庄.扩展de Bruijn图的生成树和广播[J].系统科学与数学,2003,23(1):109-116. |
| |
| 作者姓名： | 高随祥 杨德庄 |
| |
| 作者单位： | 中国科学院研究生院数学系,华罗庚应用数学与信息科学研究中心,北京,100039 |
| |
| 基金项目： | 国家自然科学基金(10171095,10001031)资助课题，中国科学院研究生院院长基金(yzjj200105)资助项目 |
| |
| 摘 要： | 扩展de Bruijn图EB(d,m;h1,h2,…,hk)是de Bruijn图的一种推广,它是一种再要的网络互连结构.本文主要研究扩展de Bruijn图中的有根生成树,证明了对任何顶点u和任意整数r:2≤r≤d,扩展de Bruijn图都有以u为根且深度为log(?),d]·max{hi:1≤i≤k}的rk-叉生成树,并由此获得了扩展de Bruijn图的广播时间的上界.
|
| 关 键 词： | 扩展de Bruijn图 生成树 广播 |
| 修稿时间： | 2000年1月9日 |
SPANNING TREES AND BROADCASTING IN EXTENDED DE BRUIJN DIGRAPH |
| |
| Sui Xiang GAO,De Zhuang YANG.SPANNING TREES AND BROADCASTING IN EXTENDED DE BRUIJN DIGRAPH[J].Journal of Systems Science and Mathematical Sciences,2003,23(1):109-116. |
| |
| Authors: | Sui Xiang GAO De Zhuang YANG |
| |
| Institution: | Mathematics Department, Graduate School of the Chinese Academy of Sciences; Hua Loo-Keng Institute of Applied Mathematics and Information Science, Beijing 100039,P.R.China |
| |
| Abstract: | Extended de Bruijn digraph EB(d, m; h1,h,2, ,hk) is an extension of de Bruijn digraph, which is an important interconnection architecture for multiple processor network systems. This paper studies the spanning trees with root of extended de Bruijn digraph. It is derived that for any extended de Bruijn digraph EB(d, m; h1,h,2, ,hk) and any integer r: 2 < r < d, there exists on rk- ary spanning tree rooted at an arbitrarily given vertex, whose depth is D logr d] . This presents an upper bound of minimum broadcasting time of the extended de Bruijn digraph. |
| |
| Keywords: | Extended de Bruijn digraph spanning tree broadcasting |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
| 点击此处可从《系统科学与数学》下载免费的PDF全文 |
|
