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

The algorithm of minimal broadcast time in network

研究信息在网络中传播的最短时间问题,建立了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.