Development of Routing Algorithms for Rotator Graphs

研究成果总结如下：-旋转图中节点到集不相交路径问题的解决，-煎饼图中节点到集不相交路径问题的解决，-烧焦煎饼图中节点到集不相交路径问题的解决，-煎饼图中节点到节点不相交路径问题的解决，-广义旋转图中节点到节点不相交路径问题的解决，-泡状排序图中节点到节点不相交路径问题的解决子串反转图中的节点到节点不相交路径问题，旋转图中容错组播路由算法的发展，以及三价Cayley图中最小反馈节点集的发展。在本研究中，我们选择了包括旋转图在内的几种Cayley图作为目标，并尝试开发即使中间计算机和/或链路发生故障也不会丢失消息发送功能的路由算法。结果，我们成功地达到了这些目标。这些结果似乎只是整个大规模并行处理系统研究领域的一小部分贡献。然而，在大规模并行处理系统的设计和开发中，拓扑的选择是最重要的问题之一，我们相信我们的研究结果对未来的研究具有重要的意义。

The research results are summarized as follows:-resolution of node-to-set disjoint paths problem in rotator graphs,-resolution of node-to-set disjoint paths problem in pancake graphs,-resolution of node-to-set disjoint paths problem in burnt pancake graphs,-resolution of node-to-node disjoint paths problem in pancake graphs,-resolution of node-to-node disjoint paths problem in generalized rotator graphs,-resolution of node-to-node disjoint paths problem in bubble-sort graphs,-resolution of node-to-node disjoint paths problem in substring reversal graphs, development of a fault-tolerant multicast routing algorithm in rotator graphs, and-development of a minimum feedback node set in trivalent Cayley graphs.In this study, we have selected several Cayley graphs including rotator graphs as targets and tried to develop routing algorithms which do not lose message sending facilities even if some faults occur with intermediate computers and/or links. As results, we have attained these objects successfully. These results seem to be only small contribution to the whole research field of the massively parallel processing systems.However, selection of topologies is one of the most important issues in design and development of the massively parallel processing systems and we are convinced that our research results have great meaning as a basis of future research.