一种基于AVBR的计算CDS的改进算法

An Improved Algorithm for Computing CDS Based on AVBR

在WuandLi算法的基础上,提出了一种有限状态机模型。利用有限状态机的状态转移、节点的颜色标记和消息的发送和接收机制,建立了可靠的并行模型,实现节点的颜色标记过程与冗余节点的删除过程的融合。算法使用新的缩减规则,减少生成的主节点数,提高了算法的性能。

This article presents a finite state machine based on Wu and Li’s algorithms. With the node color labeling and messagesending-receiving mechanism,it constructs a distributed and parallel model, and realizes the amalgamation of the marking process and the reducingprocess. With the new rules of reducing node,the amount of nodes in CDS is decreased and the approximation factor of the algorithm is improved.