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

IPSJ Web Site 1 Citations 11 References

Bibliographic Information

Other Title
  • PC クラスタ オ モチイタ 16 パンケーキグラフ ノ チョッケイ ケイサン
  • Computing the Diameters of 16-pancake Graph Using a PC Cluster

Search this article

Abstract

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

The n-pancake graph is a graph whose vertices are labeled by the permutations of n symbols. Two vertices are connected by an edge if and only if the corresponding permutations can be transitive by the prefix reverses. Since the n-pancake graph has n! vertices, it is known to be a hard problem to compute its diameter by using an algorithm with the polynomial order of the number of vertices. A fundamental approach of the diameter computation has been proposed. However, the computation of the diameter of the n-pancake graph with n=15 is the limit in practice. In order to compute the diameter of the larger pancake graphs, the search strategy in the diameter computation must be changed drastically. On top of that, it is indispensable to establish a sustainable parallel system with enough scalability. Therefore, in this study, we propose an improved algorithm to compute the diameter. We also have developed a sustainable parallel system with the Conder/MW framework, and computed the diameter of the 16-pancake graph by using a PC cluster.

Journal

Citations (1)*help

See more

References(11)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top