パンケーキグラフにおける節点から節点集合への互いに素な経路問題  [in Japanese] Node-to-Set Disjoint Paths Problem in Pancake Graphs  [in Japanese]

本論文では, パンケーキグラフにおける節点から節点集合への互いに素な経路問題に対する算法とその評価結果を与える.提案算法は, nパンケーキグラフに対して, nの多項式オーダとなる.算法は, 再帰に基づき, 類における目的節点の分布に応じて3つの場合に分けられる.パンケーキグラフのすべての節点が, 類へと分類される.得られる経路長の総和と算法の時間計算量を見積もり, 計算機シミュレーションによって確認する.

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 three 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 they are assured based on computer simulation.