Development of Routing Algorithms for Interconnection Networks based on Cayley Graphs

基于凯莱图的互联网络路由算法开发

• 批准号: 16500015
• 负责人: KANEKO Keiichi
• 金额: $ 1.28万
• 依托单位: Tokyo University of Agriculture and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2004
• 资助国家: 日本
• 起止时间: 2004 至 2006
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-16500015/
• 关键词: Transposition graphs; Bubble-sort graphs; Rotator graphs; Pancake graphs; Star graphs; node-to-set disjoint paths; node-to-node disjoint paths; Hamiltonian cycles; 不完全なパンケーキグラフ; 不完全なローテータグラフ; 素な経路; ケイリーグラフ; バイローテータグラフ; コンテナ; ハミルトニアン閉路; ハミルト

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.

研究结果总结如下：- 置换图中节点到集合不相交路径问题的算法，-气泡排序图中节点到集合不相交路径问题的算法，-双旋转图中节点到节点不相交路径问题的算法，-双旋转图中节点到集合不相交路径问题的算法，-Burnt Pancake图中节点到节点不相交路径问题的算法-不完全Pancake图的提出及其节点到节点不相交路径问题的算法，-不完全旋转图的提出及其节点到节点不相交路径问题的算法，-Pancake图中节点到集合不相交路径问题的算法，- Pancake图中的集到集不相交路问题的算法，-有缺陷的Burnt Pancake图中的Hamilton圈和Hamilton路的算法，-14-到17-Pancake图的直径的计算，以及-（n，k）-Pancake图的提出及其性能评估。我们的目标是开发算法，即使在内部节点和/或具有包括新拓扑的若干Cayley图的链路上发生某些故障，也保留发送消息的功能，并且我们已经达到了我们的目标。这些结果相对于大规模并行系统的整体研究来说可能是微不足道的。然而，拓扑结构的选择是大规模并行系统设计和实现中最重要的问题。因此，我们相信这些结果对今后的研究具有重要的意义。

项目成果

An Algorithm for Node-to-Node Disjoint Paths Problem in Burnt Pancake Graphs

烧饼图中节点到节点不相交路径问题的算法

• 发表时间: 2007
• 期刊: IEICE Transactions on Information and Systems E90-D・1
• 作者: Keiichi Kaneko;Naoki Sawada
• 通讯作者: Naoki Sawada

Node-to-Set Disjoint Paths Problem in Bi-Rotator Graphs

双旋转图中节点到集不相交路径问题

• 发表时间: 2004
• 期刊: Parallel and Distributed Processing and Applications LNCS3358
• 作者: 中山弘之;鷲崎弘宜;久保淳人;深澤良彰;K.Kaneko
• 通讯作者: K.Kaneko

Node-Disjoint Paths in a Transposition Graph

转置图中的节点不相交路径

• 发表时间: 2006
• 期刊: IEICE Transactions on Information and Systems E89-D・10
• 作者: Yasuto Suzuki;Keiichi Kaneko;Mario Nakamori
• 通讯作者: Mario Nakamori

Computing the Diameters of 16-pancake Graph Using a PC Cluster

使用 PC 集群计算 16 煎饼图的直径

• 发表时间: 2006
• 期刊: IPSJ Transactions on Mathematical Modeling and its Applications 47, SIG14(TOM15)
• 作者: Shogo Asai;Yuusuke Kounoike;Yuji Shinano;Keiichi Kaneko
• 通讯作者: Keiichi Kaneko

Container Problem in Burnt Pancake Graphs

烧焦的煎饼图中的容器问题

• 发表时间: 2005
• 期刊: Parallel and Distributed Processing and Applications LNCS 3758
• 作者: Sawada;Naoki;Yasuto Suzuki;Keiichi Kaneko
• 通讯作者: Keiichi Kaneko