一类置换群图的路由算法研究

摘要

群Cayley图是并行处理系统中研究可靠通信网络拓扑结构及路由算法的有力工具.置换群Cayley图具有结构复杂、灵活多变的特点, 而且具有良好网络所要求的性能指标.研究置换群Cayley图的路由算法是设计该类互连网络模型的重要内容之一.借助基于极小对换生成集的群Cayley图的对换树,设计了该类群Clayey图的路由算法,其时间复杂度为O(n2).同时运用置换群元素的对换分解方法,给出了两个特殊群Clayey图的最优路由算法.