Parallel Minimum Spanning Forest Algorithms on the Star and Pancake Interconnection Networks
Parallel Minimum Spanning Forest Algorithms on the Star and Pancake Interconnection Networks
复制标题
星形和饼状互连网络上的并行最小生成森林算法
DOI：
10.1007/3-540-55895-0_456
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
K. Qiu
中科院分区：
文献类型：
--
作者：
S. Akl;K. Qiu
描述了在稀疏和密集加权图中计算最小生成森林的并行算法。该算法设计用于星型和薄饼型互连网络。它们的时间复杂度与等效的超立方体算法相当，这主要归功于一种新颖的路由方案。后者统一了星型网络和煎饼网络上的数据路由，使这些网络在解决大量问题时具有与超立方体一样强大的功能，并且允许为超立方体设计的某类算法直接在星型网络和煎饼网络上实现，而不会造成时间损失。当人们回想起星形网络和煎饼网络与超立方体网络相比所具有的许多吸引人的性质，特别是它们更小的度和直径时，这些结果就显得更加重要了。
Parallel algorithms are described for computing minimum spanning forests in both sparse and dense weighted graphs. The algorithms are designed to run on the star and pancake interconnection networks. Their time complexities match those of the equivalent hypercube algorithms, thanks mainly to a novel routing scheme. The latter unifies data routing on the star and pancake networks, and makes these networks as powerful as the hypercube when solving a host of problems, and it allows a certain class of algorithms designed for the hypercube to be implemented directly on the star and pancake networks without time loss. These results take added importance when one recalls the many attractive properties that the star and pancake networks possess by comparison with the hypercube, in particular their smaller degree and diameter.