An Algorithm for Node-Disjoint Paths in Pancake Graphs
An Algorithm for Node-Disjoint Paths in Pancake Graphs
复制标题
煎饼图中节点不相交路径的算法
DOI：
--
复制
发表时间：
2003
影响因子：
0.7
通讯作者：
K. Kaneko
中科院分区：
文献类型：
--
作者：
Yasuto Suzuki;K. Kaneko
摘要 对于 n 煎饼图中的任何一对不同节点，我们给出了一种算法，用于构造连接节点的 n × 1 条内部不相交路径，时间复杂度为 n 多项式阶。对获得的每条路径的长度和算法的时间复杂度进行了理论估计并通过计算机仿真进行了验证。
SUMMARY For any pair of distinct nodes in an n-pancake graph, we give an algorithm for construction of n � 1 internally disjoint paths connecting the nodes in the time complexity of polynomial order of n. The length of each path obtained and the time complexity of the algorithm are estimated theoretically and verified by computer simulation.