基于排列图的优化广播报文算法

文章就一种特殊的图——排列图的广播算法展开讨论。首先,给出了关于排列图的一些定义。根据排列图的定义,可以知道排列图的结构具有层次性。从这一点出发,作者得出一个把排列图分成一些子图,在子图中分别广播报文的递归算法。之后,作者考虑时间复杂度和报文复杂度,得出递归算法的两点改进。最后,给出了最后的广播算法。

A Optimized Broadcasting Algorithm On Arrangement Graphs

This paper discusses adistributed broadcasting algorithm on arrangement graphs.First,It gives some definitions about the arrangement graph.According to these definitions,It knows that the arrangement graph has the hierarchical property.This paper divides the arrangement graph into some subgraphs.To which,It applies the recursive algorithm.Then,It considers the time complexity and the message complexity,and makes some improvement on the broadcasting algorithm.At last,This paper gives the complete broadcasting algorithm.