| 信息传播的最优结构 |
| |
| 引用本文： | 陈智斌,李建平.信息传播的最优结构[J].云南大学学报(自然科学版),2004,26(5):378-381. |
| |
| 作者姓名： | 陈智斌 李建平 |
| |
| 作者单位： | 云南大学,数学系,云南,昆明,650091 |
| |
| 基金项目： | 国家自然科学基金资助项目 ( 10 2 7110 3 )，云南省自然科学基金资助项目 ( 2 0 0 3F0 0 15M ) . |
| |
| 摘 要： | 研究连通网络中的信息传播问题,即有信息的节点vi在每个单位时间里能同时向它的至多ki(ki≥1)个邻点发送信息,要求传播的最短时间,使得网络中所有顶点均有此种信息.鉴于在任意网络中该问题是NP-完备的,特研究一种特殊的网络,即m维立方体网络.通过应用递推技巧,揭示了在m维立方体网络上信息传播的诸多好的特性及有趣的现象,显示了m维立方体网络是信息传播问题的最优结构.
|
| 关 键 词： | 信息传播 ki-传播模型 m维立方体网络 NP-完备 最优结构 |
| 文章编号： | 0258-7971(2004)05-0378-04 |
| 修稿时间： | 2003年10月27 |
The optimal structure of information dissemination |
| |
| CHEN Zhi-bin,LI Jian-ping.The optimal structure of information dissemination[J].Journal of Yunnan University(Natural Sciences),2004,26(5):378-381. |
| |
| Authors: | CHEN Zhi-bin LI Jian-ping |
| |
| Institution: | Department of Mathematics, Yunnan University, Kunming 650091, China |
| |
| Abstract: | The problem of information dissemination on network is studied,where any vertex vi that has information can transmits its information to at most ki(ki≥1) neighbors simultaneously per a unit time.The objective of this problem is to minimize the broadcasting time such that all vertices in the network can received this information.Since this problem is NP-complete in an arbitrary network,the special network called a hypercube of m-dimensions is studied.By using the technique of induction,many good features as well as some interesting characteristics in this hypercube are given,which shows that hypercube is the optimal structure to information dissemination. |
| |
| Keywords: | information dissemination k_i-broadcasting hypercube NP-Completeness optimal structrue |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《云南大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《云南大学学报(自然科学版)》下载免费的PDF全文 |
