PCクラスタを用いた16パンケーキグラフの直径計算

スポンサーリンク

概要

論文の詳細を見る
nパンケーキグラフは,n種類の記号で作られる順列をそれぞれ頂点とし,順列の前方反転によって移ることが可能な順列間を辺で結んだグラフである.nパンケーキグラフはn!個の頂点を持つので,頂点数に対する多項式時間のアルゴリズムでは,直径を求めることが困難な問題として知られている.これまでに,基本的な計算方法は提案されているが,実装面ではn=15の規模の計算が限界であった.さらに大規模なパンケーキグラフの直径計算を行うためには,既存の計算方法における探索戦略を根本的に変更する必要がある.また,長時間の計算を可能とする十分なスケーラビリティを持つ並列システムとしての実装が不可欠である.本研究では,より大規模なパンケーキグラフの直径を求めるために改良した計算方法を提案する.また,計算方法はConder/MWにより並列システムとして実装し,PCクラスタを利用して実際にn=16の直径を求めた.
社団法人情報処理学会の論文
2006-10-15

著者

関連論文

もっと見る

スポンサーリンク