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.

In this paper, we give an algorithm for the node-to-set disjoint paths problem in rotator graphs with its evaluation results. The algorithm is based on recursion and it is divided into cases according to the distribution of destination nodes in classes into which all the nodes in a rotator graph are categorized. The sum of the length of paths obtained and the time complexity of the algorithm are estimated and verified by computer simulation.

Bubble-sort graphs are variants of Cayley graphs. A bubble-sort graph is suitable as a topology for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on n-bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between two arbitrary nodes in time bounded by a polynomial in n, the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of the path lengths after proving the correctness of the algorithm. In addition, we report the results of computer experiments evaluating the average performance of the algorithm.

A minimum feedback node set in a graph is a minimum node subset whose deletion makes the graph acyclic. Its detection in a dependency graph is important to recover from a deadlock configuration. A livelock configuration is also avoidable if a check point is set in each node in the minimum feedback node set. Hence, its detection is very important to establish dependable network systems. In this letter, we give a minimum feedback node set in a trivalent Cayley graph. Assuming that each word has n bits, for any node, we can judge if it is included in the set or not in constant time.

In this paper, we give an algorithm for the node-to-set disjoint paths problem in a transposition graph. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided into two cases according to the distribution of destination nodes. The maximum length of each path and the time complexity of the algorithm are estimated theoretically to be O(n7) and 3n - 5, respectively, and the average performance is evaluated based on computer experiments.

In this paper, we give an algorithm for the node-to-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.