焦げたパンケーキグラフの内素な経路問題(高信頼システム, SWOPP武雄2005(2005年並列/分散/協調処理に関する「武雄」サマー・ワークショップ))
スポンサーリンク
概要
- 論文の詳細を見る
次数nの焦げたパンケーキグラフ[1]は, n!×2^n個の節点を持ったグラフであり, ハイパーキューブなどと比べて集積度が高いこと, パンケーキグラフやスターグラフ, ローテータグラフなどとは異なる節点数を結合できることから, 相互結合網の位相として注目を集めている.本研究では, 焦げたパンケーキグラフの任意の2節点に対して, 次数の多項式時間で, 次数と同じ本数の内素な経路を作成するアルゴリズムを提案する.さらに本稿では, 提案された算法が与える時間計算量と最大経路長が, それぞれO(n^3)および3n+4であることもあわせて示す.計算機シミュレーションの結果, 平均時間計算量, 最大経路長はそれぞれO(n^<2.6>), 3n+4となった.
- 社団法人電子情報通信学会の論文
- 2005-07-29
著者
関連論文
- 5M-4 パンケーキグラフにおける節点対間の互いに素な耐クラスタ故障経路選択アルゴリズム(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- 異なる方式に基づく英単語学習用システムの開発と評価
- 5M-5 焦げたパンケーキグラフにおける耐故障経路選択アルゴリズム(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- D-1-3 焦げたパンケーキグラフの改善(D-1. コンピュテーション,一般セッション)
- (n,k)-パンケーキグラフとその特性(アルゴリズム理論)
- 17パンケーキグラフの直径計算(パラレルコンピューティングの応用)
- 自律協調型語彙学習環境における携帯電話による教材投稿システム (教育・学習支援におけるSNSの利活用/一般)
- PCクラスタを用いた16パンケーキグラフの直径計算
- パンケーキグラフの直径を求める耐障害性のある並列計算システム(セッション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技術/一般)
- D-10-17 SIMD型拡張命令を利用した並列3値論理シミュレーション
- ネットワーク対戦型ゲームに基づく教育システムの開発(Collaborationとagent技術/一般)
- トリバレントケイリーグラフにおける最小フィードバック頂点集合
- ローテータグラフにおける耐故障マルチキャスト経路選択問題
- ローテータグラフにおける耐故障マルチキャスト経路選択問題
- 焦げたパンケーキグラフにおける節点から節点集合への互いに素な経路問題
- 教育用論理回路シミュレータの試作
- パンケーキグラフにおける節点から節点集合への互いに素な経路問題
- パンケーキグラフにおける頂点間の内素な経路の構成算法
- ハイパキューブ相互結合網のための耐故障マルチキャスト経路選択算法
- D-10-16 ハイパーキューブのための耐故障マルチキャスト算法
- ローテータグラフにおける頂点から頂点集合への互いに素な経路問題
- D-10-3 ローテータグラフにおける節点から集合への互いに素な経路問題
- D-6-7 HaskellコンパイラGHCの出力オブジェクトの改良
- 移動体環境における誤り回復方式の提案
- 階層型ハイパーキューブ網の耐故障ルーティングアルゴリズム
- 階層型ハイパキューブ相互結合網におけるルーティングアルゴリズム
- 4L-5 STG機械における閉包の新しい表現方法
- 4L-4 Marlowの更新回避解析の改善の実装と評価
- D-10-5 相互結合網における新しいデッドロック回復機構
- D-10-4 有向経路選択能力に基づくハイパキューブの耐故障経路選択算法の停止性
- モバイルネットワーク環境における移動距離を考慮した誤り回復方式の提案
- ハイパキューブの耐故障経路選択算法の耐リンク故障への拡張
- D-10-12 モバイル環境における移動距離に基づく誤り回復方式
- D-6-12 HHC網におけるルーティングアルゴリズムの改良
- モバイルネットワーク環境における誤り回復方式の提案
- マルチプロセッサ型計算機における効率的なチェックポイント方式の提案
- モバイルネットワーク環境における誤り回復方式の提案
- マルチプロセッサ型計算機における新しいチェックポイント方式
- ハイパキューブの耐故障経路選択算法の評価
- 次数が一定な階層型完全結合網の提案
- 全到達可能性によるハイパキューブの耐故障経路選択算法
- 階層型完全結合キューブ網
- ハイパキューブ結合網の耐故障経路選択算法
- WWWを利用した個人適応型CAIシステム方式の提案(教育情報の解析と数理モデル/一般)
- ハイパキューブの耐故障経路選択算法の拡張
- 再構成可能な次世代計算機アーキテクチャの基礎検討
- VLSIにおける全数入力テストのための検査点挿入算法
- GAによるパストランジスタ論理回路のテストパターン生成
- フォートトレラント階層型ニュラルネットワークの動的構成
- 階層型ニューラルネットワークのフォールトトレラント学習
- ハイパキューブにおける耐故障経路選択算法
- SIMD型計算機における新しいチェックポイント方式
- 収束可制御性を用いたパーシャルスキャン FF の選択手法
- Marlowの更新回避解析の改善
- 自己簡約グラフによる結合子式の評価
- 完全遅延評価に適した関数プログラムの共有解析
- 関数プログラムのコンパイラにおける型情報を用いた効率的な共有解析の実現
- パーソナルコンピュータ上のUtiLispシステム
- D-15-1 二次関数のグラフ作画支援システム(D-15.教育工学,一般セッション)
- 部分列反転グラフにおける内素な経路(情報・システム基礎)
- D-15-13 二言語間チャットシステムにおける誤訳認知支援(D-15.教育工学,一般セッション)
- Scaffoldingを利用した確率学習支援システムの開発とその利用
- 関連画像提示による日英自動翻訳チャットシステムにおける誤訳認知
- 関連画像提示による日英自動翻訳チャットシステムにおける誤訳認知
- 関連画像提示による日英自動翻訳チャットシステムにおける誤訳認知