パンケーキグラフの直径計算

• Item type: Trans(1)
• 公開日: 2005-06-15
• タイトル: パンケーキグラフの直径計算
• タイトル / 言語: en
• タイトル: Computing the Diameters of Pancake Graphs
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: オリジナル論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 東京農工大学工学部情報コミュニケーション工学科
• 著者所属: 東京農工大学工学部情報コミュニケーション工学科
• 著者所属: 東京農工大学工学部情報コミュニケーション工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Information and Communication Sciences Faculty of Engineering Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Information and Communication Sciences Faculty of Engineering Tokyo University of Agriculture and Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Information and Communication Sciences Faculty of Engineering Tokyo University of Agriculture and Technology
• 著者名: 鴻池, 祐輔; 金子, 敬一; 品野, 勇治
• 著者名(英): Yuusuke, Kounoike; Keiichi, Kaneko; Yuji, Shinano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: n パンケーキグラフは，n 種類の記号で作られる順列をそれぞれ頂点とし，順列の前方反転によって移ることが可能な順列間を辺で結んだグラフである．n パンケーキグラフはn! 個の頂点を持つので，頂点数に対する多項式時間のアルゴリズムでは，14 パンケーキグラフの直径でさえ求めることが困難な問題として知られている．実際に，これまでに求められている直径はn = 13 までである．本稿では，Heydari らが13 パンケーキグラフの直径を求めるときに使った手法を基本として，不要な探索を行わないように発展させた手法を提案し，n = 14，15 のパンケーキグラフの直径を与えた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 46, 号 SIG10(TOM12), p. 48-56, 発行日 2005-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会