17パンケーキグラフの直径計算(<特集>パラレルコンピューティングの応用)
スポンサーリンク
概要
- 論文の詳細を見る
すべて大きさの異なる17枚のパンケーキに対する整列問題を解くことは,17パンケーキグラフの直径を求めることと同値である.17パンケーキグラフは,次数16の対称グラフである.しかしながら,頂点数が300兆を超えるため,頂点数や辺数に依存する単純なアルゴリズムによって直径を求めようとしても,計算時間と記憶容量の制限により,現実的にはまったく歯が立たない.ここでは,アルゴリズムの改良とともに,100台以上のPCとCondor-MWを用いた並列計算によって17パンケーキグラフの直径計算に挑んだ様子を紹介する.その結果については,本文を参照されたい.
- 2007-10-01
著者
-
品野 勇治
東京農工大学
-
金子 敬一
東京農工大学工学府
-
品野 勇治
東京農工大学 工学部 情報コミュニケーション工学科
-
品野 勇治
東京農工大学大学院共生科学技術研究院
-
金子 敬一
東京農工大 大学院工学府
関連論文
- 5M-4 パンケーキグラフにおける節点対間の互いに素な耐クラスタ故障経路選択アルゴリズム(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- 列生成法を用いたナーススケジューリング問題の解法
- 異なる方式に基づく英単語学習用システムの開発と評価
- 5M-5 焦げたパンケーキグラフにおける耐故障経路選択アルゴリズム(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- D-1-3 焦げたパンケーキグラフの改善(D-1. コンピュテーション,一般セッション)
- (n,k)-パンケーキグラフとその特性(アルゴリズム理論)
- 17パンケーキグラフの直径計算(パラレルコンピューティングの応用)
- 自律協調型語彙学習環境における携帯電話による教材投稿システム (教育・学習支援におけるSNSの利活用/一般)
- 混合整数線形計画法を用いた距離画像の位置合わせ
- 大規模分枝限定木可視化のための適応的木構造グラフ生成(Session 2)
- 単語長を考慮した最長しりとり問題の実験的考察
- 文字数最大しりとり問題の解法
- 最大長しりとり問題の解法
- 準最適解からの加重文脈自由文法の獲得(セッション4)
- 最長しりとり問題とその解法(OR研究の最前線)
- 2-D-4 誤差の離散性を考慮したレンズ調整のロバスト最適化(離散・組合せ最適化(6))
- 分散遺伝的アルゴリズムとローカルサーチを併用した大学の時間割作成システム
- ピュアP2Pネットワーク上における分枝限定法の並列化 : Churn発生時の耐故障性の研究
- 制約2次計画法および2次錐計画法を用いた半導体露光装置用レンズの最適調整(機械力学,計測,自動制御)
- 半導体露光装置におけるレンズ調整 : 群回し調整の最適化(機械力学,計測,自動制御)
- 混合整数計画ソルバーの並列化(パラレルコンピューティングの応用)
- 混合整数線形計画問題を用いた階層的な距離画像の位置合わせ(セッション6)
- 半導体露光装置におけるディストーション調整の最適化(機械力学,計測,自動制御)
- PCクラスタを用いた16パンケーキグラフの直径計算
- 2次割当て問題への適用におけるIntegral Basis Methodの改良の提案
- 分枝限定法における計算過程の可視化(セッション3)
- Particle Swarm Optimizationによる結像光学系の最適化(セッション2)
- 2-F-10 Integral Basis Methodにおける変数選択規則と緩和問題(数理計画(2))
- パンケーキグラフの直径を求める耐障害性のある並列計算システム(セッション3)
- 2次割当問題への適用によるIntegral Basis Methodの改良の提案(セッション3)
- D-15-4 抽象語に関連する画像検索システムの提案(D-15.教育工学,一般セッション)
- 2ZB-5 プログラミングにおけるポインタ操作を通した関数学習機能(プログラミング教育・ロボット・動画・仮想空間を用いた教育,学生セッション,コンピュータと人間社会)
- 故障をもつ焦げたパンケーキグラフにおけるハミルトニアン経路と閉路
- 音高と音価に着目した読譜学習システムの設計と実現
- D-15-7 数学における二次関数のグラフ学習支援システムの設計と試作(D-15.教育工学,一般セッション)
- D-15-15 動画教材を用いた語彙学習システム(D-15. 教育工学,一般セッション)
- D-1-7 アミノ酸配列における近似パタン検索アルゴリズムに関する研究(D-1. コンピュテーション,一般セッション)
- 計算機アーキテクチャ教育支援システムの開発と協調学習への適用(教育システムにおけるプラットホームとコンテンツ開発論文)
- 計算機アーキテクチャ教育用ビジュアルシミュレータの組み込みメイル機能(情報教育,情報教育〜理念・理論・実践〜)
- パンケーキグラフにおける半素な耐クラスタ故障経路選択(分散システム)
- D-15-24 iPodを用いた単語学習システムの開発と評価(D-15.教育工学,一般講演)
- D-15-23 単語学習用コンテンツの生成支援システム(D-15.教育工学,一般講演)
- D-1-7 n-パンケーキグラフP_nにおけるk組の互いに素な経路問題(D-1.コンピュテーション,一般講演)
- D-1-6 塩基配列の局所的な類似文字列検索アルゴリズム(D-1.コンピュテーション,一般講演)
- 携帯用音楽端末を用いた単語学習システムの開発と評価(教育におけるセキュリティ/一般)
- ノイマン型コンピュータ教材を用いた計算機アーキテクチャ教育支援環境
- A_013 (n,k)-パンケーキグラフにおけるハミルトン閉路(A分野:モデル・アルゴリズム・プログラミング)
- A_012 不完全なスターグラフの新しい構成と経路選択算法(A分野:モデル・アルゴリズム・プログラミング)
- 不完全なパンケーキグラフと経路問題(ネットワーク,SWoPP2006)
- D-15-4 読譜学習システムの実現(D-15.教育工学,一般講演)
- D-1-2 (n,k)パンケーキグラフとその性質(D-1.コンピュテーション,一般講演)
- 数学の文章題を解くための作図支援システムの開発
- N-018 プログラミングにおけるポインタ操作学習のための支援システム(N分野:教育・人文科学)
- C-032 耐故障関数型言語処理系の実現(C分野:アーキテクチャ・ハードウェア)
- A-032 焦げたパンケーキグラフにおけるコンテナ問題(A分野:モデル・アルゴリズム・プログラミング)
- 焦げたパンケーキグラフの内素な経路問題(高信頼システム, SWOPP武雄2005(2005年並列/分散/協調処理に関する「武雄」サマー・ワークショップ))
- パンケーキグラフの直径計算
- バブルソートグラフにおける素な経路選択アルゴリズム(アルゴリズム理論)
- バブルソートグラフにおける耐故障経路選択アルゴリズム(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004))
- トランスポジショングラフにおける素な経路
- n ≥ 14パンケーキグラフの直径計算
- 教育用計算機システムシミュレータED21の設計と評価
- バブルソートグラフにおける節点間の内素な経路問題(2003年並列/分散/協調処理に関する「松江」サマーワークショップ(SWoPP松江2003))(DC-1高信頼化手法)
- MMX命令を利用したビット並列化塩素配列照合アルゴリズム
- 学習用メタデータを含む電子教科書のためのWebブラウザの試作(Collaborationとagent技術/一般)
- 最長しりとり問題の解法
- 方形チップ格子上のウェーハ配置最適化(VLSI設計技術とCAD)
- 方形チップ格子上のウェーハ配置最適化
- 取得チップ数を最大化するウエハ配置(ケース・スタディ)
- D-10-17 SIMD型拡張命令を利用した並列3値論理シミュレーション
- ネットワーク対戦型ゲームに基づく教育システムの開発(Collaborationとagent技術/一般)
- トリバレントケイリーグラフにおける最小フィードバック頂点集合
- ローテータグラフにおける耐故障マルチキャスト経路選択問題
- ローテータグラフにおける耐故障マルチキャスト経路選択問題
- 焦げたパンケーキグラフにおける節点から節点集合への互いに素な経路問題
- 教育用論理回路シミュレータの試作
- パンケーキグラフにおける節点から節点集合への互いに素な経路問題
- パンケーキグラフにおける頂点間の内素な経路の構成算法
- ハイパキューブ相互結合網のための耐故障マルチキャスト経路選択算法
- D-10-16 ハイパーキューブのための耐故障マルチキャスト算法
- ローテータグラフにおける頂点から頂点集合への互いに素な経路問題
- D-10-3 ローテータグラフにおける節点から集合への互いに素な経路問題
- D-6-7 HaskellコンパイラGHCの出力オブジェクトの改良
- 移動体環境における誤り回復方式の提案
- 分枝限定法における分枝戦略選択のための計算過程の可視化
- 2次割当問題に対するIntegral Basis Method(離散最適化)
- CPLEX MIP OptimizerのPUBB2フレームワークによる並列化について(整数計画(2))
- 混合整数計画問題の解法における前処理の効果検証(整数計画(2))
- 2108 半導体露光装置におけるディストーション補正の最適化(OS21 設計と最適化II)
- 半導体露光装置のステージ格子計測法
- メッセージ遅延の影響評価のための並列分散プログラムシミュレータの研究
- メッセージ遅延の影響評価のための並列分散プログラムシミュレータの研究
- 確率的なグラフ連結性判定アルゴリズム
- 電子部品装着機の装着順序決定アルゴリズムの研究
- 不完全な部品の組合せ問題について(II) : 誤差がベクトルの場合
- メモリ領域が小さい確率的なグラフ連結性判定アルゴリズムについて
- 分枝限定法並列化ツールPUBB (アルゴリズム工学)
- PCクラスタを用いたHEXにおける最善応手手順の生成(組合せ最適化(1))
- PUBBによるPCクラスタ環境における並列分枝限定法 (新しいパラダイムとしてのアルゴリズム工学)
- PCクラスタ環境における並列分枝限定法(数理計画(2))