パンケーキグラフの直径を求める耐障害性のある並列計算システム(セッション3)
スポンサーリンク
概要
- 論文の詳細を見る
nパンケーキグラフは, n種類の記号で作られる順列をそれぞれ頂点とし, 順列の前方反転によって移ることが可能な順列間を辺で結んだグラフである.nパンケーキグラフはn!個の頂点を持つので, 頂点数に対する多項式時間のアルゴリズムでは, 直径を求めるのが困難な問題として知られている.これまでに, 基本的な計算方法は提案されているが, 実装面ではn=15の規模の計算が限界であった.さらに大規模なパンケーキグラフの直径計算を行うためには, 十分なスケーラビリティを持つ並列システムの構築が不可欠である.本研究では, 大規模なパンケーキグラフの直径計算が行える耐障害性のある並列システムを開発し, 遊休計算機を利用して実際にn=16の直径を求めた.
- 社団法人情報処理学会の論文
- 2005-09-21
著者
-
品野 勇治
東京農工大学
-
金子 敬一
東京農工大学工学府
-
鴻池 祐輔
キヤノン株式会社
-
品野 勇治
東京農工大学院共生科学技術研究部
-
浅井 章吾
東京農工大学工学部情報工学科
-
鴻池 祐輔
東京農工大学工学部情報工学科
-
金子 敬一
東京農工大 大学院工学府
-
浅井 章吾
東京農工大学工学部情報コミュニケーション工学科
関連論文
- 5M-4 パンケーキグラフにおける節点対間の互いに素な耐クラスタ故障経路選択アルゴリズム(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- 列生成法を用いたナーススケジューリング問題の解法
- 異なる方式に基づく英単語学習用システムの開発と評価
- 5M-5 焦げたパンケーキグラフにおける耐故障経路選択アルゴリズム(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- D-1-3 焦げたパンケーキグラフの改善(D-1. コンピュテーション,一般セッション)
- (n,k)-パンケーキグラフとその特性(アルゴリズム理論)
- 17パンケーキグラフの直径計算(パラレルコンピューティングの応用)
- 自律協調型語彙学習環境における携帯電話による教材投稿システム (教育・学習支援におけるSNSの利活用/一般)
- 混合整数線形計画法を用いた距離画像の位置合わせ
- 大規模分枝限定木可視化のための適応的木構造グラフ生成(Session 2)