网络中信息传播的最短时间算法  

The algorithm of minimal broadcast time in network

作　　者：陈智斌[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2003年第6期483-486,共4页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学研究基金资助项目(10271103);云南省教育厅科学研究基金资助项目(0112156).

摘　　要：研究信息在网络中传播的最短时间问题,建立了ki-传播模型,即有信息的节点vi在每个时间单位里能同时向它的至多ki(ki≥1)个邻点发送信息,要求传播的最短时间,使得网络的所有顶点均有此种信息.指出了该问题在任意网络中是NP-完备的,对该问题给出了一个多项式时间算法来求解在树状网络中信息传播的最短时间,并且能够求出树状网络的传播中心.The problem of minimizing broadcasting time in network was considered and a model of kibroadcasting was given,that is,for each vertex vi∈V this vertex vi has the information can transmit its information to at most ki 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.

关 键 词：信息传播 最短时间 算法 树状网络 传播中心 

分 类 号：O157.6[理学—数学] TP301.5[理学—基础数学]