不完全なパンケーキグラフと経路問題

摘要

パンケーキグラフは，並列計算機の相互結合網のための位相として提案され，小さな直径や次数で多くのノードを結合できる利点を持つ．しかしながら，とりうるノード数が整数の階乗であるため，逐次的拡張性に乏しいという欠点を持つ．本論文では，パンケーキグラフにおいていくつかの部分グラフを開放除去することで得られるグラフを提案し，そのグラフに対して，ユニキャスト経路選択問題，ハミルトン閉路問題，ハミルトン経路問題，コンテナ問題解くアルゴリズムを与える．