Node-to-set disjoint paths problem in pancake graphs
Node-to-set disjoint paths problem in pancake graphs
复制标题
煎饼图中节点到集不相交路径问题
DOI：
--
复制
发表时间：
2003
影响因子：
0.7
通讯作者：
Yasuto Suzuki
中科院分区：
文献类型：
--
作者：
K. Kaneko;Yasuto Suzuki
在本文中，我们给出了煎饼图中节点到集不相交路径问题的算法及其评估结果。对于 n 煎饼图，该算法具有 n 阶多项式。它基于递归，根据目标节点在煎饼图中所有节点所属类中的分布情况分为两种情况。估计所获得的路径长度之和以及算法的时间复杂度，并基于计算机模拟评估平均性能。关键词: 互连网络, 图算法, 煎饼图, 节点到集不相交路径, 并行计算
In this paper, we give an algorithm for the nodeto-set disjoint paths problem in pancake graphs with its evaluation results. The algorithm is of polynomial order of n for an n-pancake graph. It is based on recursion and divided into two cases according to the distribution of destination nodes in classes into which all the nodes in a pancake graph are categorized. The sum of lengths of paths obtained and the time complexity of the algorithm are estimated and the average performance is evaluated based on computer simulation. key words: interconnection networks, graph algorithms, pancake graph, node-to-set disjoint paths, parallel computing