パンケーキグラフの直径計算  [in Japanese] Computing the Diameters of Pancake Graphs  [in Japanese]

Access this Article

Search this Article

Author(s)

    • 鴻池 祐輔 KOUNOIKE YUUSUKE
    • 東京農工大学工学部情報コミュニケーション工学科 Department of Computer, Information and Communication Sciences, Faculty of Engineering, Tokyo University of Agriculture and Technology
    • 金子 敬一 KANEKO KEIICHI
    • 東京農工大学工学部情報コミュニケーション工学科 Department of Computer, Information and Communication Sciences, Faculty of Engineering, Tokyo University of Agriculture and Technology
    • 品野 勇治 SHINANO YUJI
    • 東京農工大学工学部情報コミュニケーション工学科 Department of Computer, Information and Communication Sciences, Faculty of Engineering, Tokyo University of Agriculture and Technology

Abstract

n パンケーキグラフは,n 種類の記号で作られる順列をそれぞれ頂点とし,順列の前方反転によって移ることが可能な順列間を辺で結んだグラフである.n パンケーキグラフはn! 個の頂点を持つので,頂点数に対する多項式時間のアルゴリズムでは,14 パンケーキグラフの直径でさえ求めることが困難な問題として知られている.実際に,これまでに求められている直径はn = 13 までである.本稿では,Heydari らが13 パンケーキグラフの直径を求めるときに使った手法を基本として,不要な探索を行わないように発展させた手法を提案し,n = 14,15 のパンケーキグラフの直径を与えた.The n-pancake graph is a graph whose vertices are labeled by permutations on n symbols. There is an edge between two vertices when the label of one vertex is derived from the other by some prefix reversal. Finding the diameter of the n-pancake graph is known to be a very hard problem, because n-pancake graph has n! vertices. Actually, n = 13 has been the maximum size of the n-pancake graph of which diameter was known so far. Heydari et al. found the diameter of the 13-pancake graph by using their own method. In this paper, we extend their method and give diameters of 14- and 15-pancake graphs that are previously unknown by using it.

The n-pancake graph is a graph whose vertices are labeled by permutations on n symbols. There is an edge between two vertices when the label of one vertex is derived from the other by some prefix reversal. Finding the diameter of the n-pancake graph is known to be a very hard problem, because n-pancake graph has n! vertices. Actually, n=13 has been the maximum size of the n-pancake graph of which diameter was known so far. Heydari et al. found the diameter of the 13-pancake graph by using their own method. In this paper, we extend their method and give diameters of 14- and 15-pancake graphs that are previously unknown by using it.

Journal

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

    情報処理学会論文誌数理モデル化と応用(TOM) 46(SIG10(TOM12)), 48-56, 2005-06-15

    Information Processing Society of Japan (IPSJ)

References:  17

Cited by:  2

Codes

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