Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs
Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs
复制标题
DOI：
--
复制
发表时间：
2002-08
期刊：
影响因子：
--
通讯作者：
K. Kaneko
中科院分区：
文献类型：
--
作者：
K. Kaneko
焦饼图是Cayley图的一个变体，它的拓扑结构适合于大规模并行系统。然而，对于焦饼图，还有很大的研究空间。因此，在这项研究中，我们专注于n-burned煎饼图，并提出了一个算法，以获得从一个源节点到n个目的地节点的n个不相交的路径在多项式阶时间的n，n是图的程度。此外，我们估计了算法的时间复杂度和路径长度之和。我们也给出了算法的正确性证明。此外，我们报告的计算机模拟的结果，以评估该算法的平均性能。关键词：烧饼图，不相交路径，多项式算法，容错，路由算法
A burnt pancake graph is a variant of Cayley graphs and its topology is suitable for massively parallel systems. However, for a burnt pancake graph, there is much room for further research. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order time of n, n being the degree of the graph. In addition, we estimate the time complexity of the algorithm and the sum of path lengths. We also give a proof of correctness of the algorithm. Moreover, we report the results of computer simulation to evaluate the average performance of the algorithm. key words: burnt pancake graph, disjoint paths, polynomial algorithm, fault tolerance, routing algorithm