PCクラスタを用いた16パンケーキグラフの直径計算  [in Japanese] Computing the Diameters of 16-pancake Graph Using a PC Cluster  [in Japanese]

Access this Article

Search this Article

Author(s)

    • 浅井 章吾 ASAI SHOGO
    • 東京農工大学工学部情報工学科 Department of Computer and Information Sciences, Tokyo University of Agriculture and Technology
    • 鴻池 祐輔 KOUNOIKE YUUSUKE
    • 東京農工大学工学部情報工学科 Department of Computer and Information Sciences, Tokyo University of Agriculture and Technology
    • 品野 勇治 [他] SHINANO YUJI
    • 東京農工大学工学部情報工学科 Department of Computer and Information Sciences, Tokyo University of Agriculture and Technology
    • 金子 敬一 KANEKO KEIICHI
    • 東京農工大学工学部情報工学科 Department of Computer and Information Sciences, Tokyo University of Agriculture and Technology

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.

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

  • 情報処理学会論文誌数理モデル化と応用(TOM)

    情報処理学会論文誌数理モデル化と応用(TOM) 47(SIG14(TOM15)), 71-79, 2006-10-15

    Information Processing Society of Japan (IPSJ)

References:  11

Cited by:  1

Codes

  • NII Article ID (NAID)
    110004856979
  • NII NACSIS-CAT ID (NCID)
    AA11464803
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7780
  • NDL Article ID
    8553244
  • NDL Call No.
    Z74-C192
  • Data Source
    CJP  CJPref  NDL  NII-ELS  IPSJ 
Page Top