陈智斌, 李建平. 信息传播的最优结构[J]. 云南大学学报(自然科学版), 2004, 26(5): 378-381.
引用本文: 陈智斌, 李建平. 信息传播的最优结构[J]. 云南大学学报(自然科学版), 2004, 26(5): 378-381.
CHEN Zhi-bin, LI Jian-ping. The optimal structure of information dissemination[J]. Journal of Yunnan University: Natural Sciences Edition, 2004, 26(5): 378-381.
Citation: CHEN Zhi-bin, LI Jian-ping. The optimal structure of information dissemination[J]. Journal of Yunnan University: Natural Sciences Edition, 2004, 26(5): 378-381.

信息传播的最优结构

The optimal structure of information dissemination

  • 摘要: 研究连通网络中的信息传播问题,即有信息的节点vi在每个单位时间里能同时向它的至多ki(ki≥1)个邻点发送信息,要求传播的最短时间,使得网络中所有顶点均有此种信息.鉴于在任意网络中该问题是NP-完备的,特研究一种特殊的网络,即m维立方体网络.通过应用递推技巧,揭示了在m维立方体网络上信息传播的诸多好的特性及有趣的现象,显示了m维立方体网络是信息传播问题的最优结构.

     

    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.

     

/

返回文章
返回