パンケーキグラフの直径計算 [in Japanese] Computing the Diameters of Pancake Graphs [in Japanese]
Access this Article
Search this Article
Author(s)
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)