Development of Routing Algorithms for Interconnection Networks based on Cayley Graphs

研究成果总结如下：-转置图中节点到集不相交路径问题的算法，-泡状排序图中节点到集不相交路径问题的算法，-双旋转图中节点到集不相交路径问题的算法，-烧焦煎饼图中节点到节点不相交路径问题的算法-不完全煎饼图的提出和节点到节点不相交路径的算法——其中不完全旋转图的提出和节点到节点不相交路径问题的算法，——煎饼图中节点到集合不相交路径问题的算法，——煎饼图中集合到集合不相交路径问题的算法，——错误烧焦煎饼图中哈密顿循环和哈密顿路径的算法，——14 ~ 17张煎饼图直径的计算，——（n, k）张煎饼图的提出及其性能评价。在这项研究中，我们的目标是开发一种算法，即使在内部节点和/或包含新拓扑的几个Cayley图上发生一些故障，也能保留发送消息的功能，并且我们已经达到了我们的目标。这些结果与整个大规模并行系统的研究活动相比，可能是很小的贡献。然而，在大规模并行系统的设计和实现中，拓扑的选择是最重要的问题。因此，我们相信这些结果对未来的研究具有重要的意义。

Research results are summarized as follows:- Algorithm for node-to-set disjoint paths problem in Transposition graphs,- Algorithm for node-to-set disjoint paths problem in Bubble-sort graphs,- Algorithm for node-to-node disjoint paths problem in Bi-rotator graphs,- Algorithm for node-to-set disjoint paths problem in Bi-rotator graphs,- Algorithm for node-to-node disjoint paths problem in Burnt Pancake graphs- Proposal of Incomplete Pancake graphs and Algorithm for node-to-node disjoint paths problem in them,- Proposal of Incomplete Rotator graphs and Algorithm for node-to-node disjoint paths problem in them,- Algorithm for node-to-set disjoint paths problem in Pancake graphs,- Algorithm for set-to-set disjoint paths problem in Pancake graphs,- Algorithm for Hamiltonian cycles and Hamiltonian paths in faulty Burnt Pancake graphs,- Computation of diameters of 14- to 17-Pancake graphs, and- Proposal of (n, k)-Pancake graphs and their performance evaluation.In this study, we aimed to develop algorithms that retain the functions to send messages even if some faults occur on internal nodes and/or links with several Cayley graphs including new topologies, and we have attained our goals. These results may be small contributions compared to the whole research activities with respect to the massively parallel systems. However, selection of topologies is the most important issue in the design and implementation of the massively parallel systems. Therefore, we are convinced that these results have great meaning as foundation of the future researches.