Node-to-set disjoint paths problem in pancake graphs
Keiichi Kaneko, Yasuto Suzuki · IEICE Transactions on Information and Systems · 2003
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