| 网络中信息传播的最短时间算法 |
| |
| 引用本文： | 陈智斌.网络中信息传播的最短时间算法[J].云南大学学报(自然科学版),2003,25(6):483-486. |
| |
| 作者姓名： | 陈智斌 |
| |
| 作者单位： | {{if article.pacs && article.pacs != '}}PACS: {{article.pacs}}{{/if}} |
| |
| 基金项目： | 国家自然科学研究基金资助项目(10271103)，云南省教育厅科学研究基金资助项目(0112156). |
| |
| 摘 要： | 研究信息在网络中传播的最短时间问题,建立了ki-传播模型,即有信息的节点vi在每个时间单位里能同时向它的至多ki(ki≥1)个邻点发送信息,要求传播的最短时间,使得网络的所有顶点均有此种信息.指出了该问题在任意网络中是NP-完备的,对该问题给出了一个多项式时间算法来求解在树状网络中信息传播的最短时间,并且能够求出树状网络的传播中心.
|
| 关 键 词： | 信息传播 网络 树状网络 最短时间 传播中心 算法 |
| 文章编号： | 0258-7971(2003)06-0483-04 |
| 修稿时间： | 2003年5月7日 |
The algorithm of minimal broadcast time in network |
| |
| CHEN Zhi-bin.The algorithm of minimal broadcast time in network[J].Journal of Yunnan University(Natural Sciences),2003,25(6):483-486. |
| |
| Authors: | CHEN Zhi-bin |
| |
| Institution: | {{if article.pacs && article.pacs != '}}PACS: {{article.pacs}}{{/if}} |
| |
| Abstract: | The problem of minimizing broadcasting time in network was considered and a model of ki broadcasting was given,that is,for each vertex vi ∈V this vertex vi has the information can transmit its information to at most ki neighbors per a unit time.The objective of the problem is to minimize the broadcasting time such that all vertex in the network obtain this information.It is pointed out that the problem is NP-completeness.A polynomial time algorithm was constructed to determine the minimal broadcasting time from the fixed vertex u and the broadcasting center in a hierarchical network is found. |
| |
| Keywords: | information dissemination network hierarchical network minimal broadcast time broadcast center algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《云南大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《云南大学学报(自然科学版)》下载免费的PDF全文 |
