スタックを用いた幅優先探索に関する並列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本稿では, 並列化困難な問題として知られているP完全問題の一つである, スタックを用いた幅優先探索の並列性について検証する.まず, 入力グラフの最大次数が3であるようなスタックを用いた幅優先探索もP完全となることを示す.次に, スタックを用いた幅優先探索のP完全性を表す尺度として最長経路距離を導入し, この尺度を用いて, 効率の良い並列アルゴリズムの提案を行う.このアルゴリズムの計算量により, l=O(log^n)の場合, スタックを用いた幅優先探索がクラスNCに属することを示す.ここで, n, lはそれぞれ入力サイズおよび最長経路距離であり, kは正の整数とする.また, このアルゴリズムはl=O(n^ε), 0<ε<1の場合にコスト最適な並列アルゴリズムとなる.
- 社団法人電子情報通信学会の論文
- 2001-11-09
著者
関連論文
- D-1-11 非同期膜計算による充足可能性問題とハミルトン路問題の解法(D-1.コンピュテーション,一般セッション)
- DNA計算における対数時間ソートアルゴリズム
- ヘテロジニアスBSPモデル上の2次元データ分割
- 選択問題を解くBSPモデル及びBSP^*モデル上の並列アルゴリズム
- 2値画像上の全最近点を求めるBSPモデル上の並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム(並列・分散)
- 選択問題を解くBSPモデルおよびBSPモデル上の並列アルゴリズム
- D-1-2 GRID 環境に適した効率の良い完全交換アルゴリズム
- 膜計算における基本演算アルゴリズム
- 検知領域交点を考慮した連結センサカバーアルゴリズム
- DNA計算による浮動小数点演算アルゴリズム
- 最小スループット制御を行うアクセスポイント選択手法
- A-006 局所探索を用いた集中型アクセスポイント選択アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- A-005 DNA計算におけるMAX-SATの解法(A分野:モデル・アルゴリズム・プログラミング)
- A-004 重み付けを用いた分散型アクセスポイント選択アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- A-003 DNA計算における乗算および除算アルゴリズム(A分野:モデル・アルゴリズム・プログラミング)
- 無線LANにおけるAP選択戦略に関する検討(NW性能管理,NW品質,一般)
- 無線LANにおけるAP選択戦略に関する検討(NW性能管理,NW品質,一般)
- DNA計算における対数時間ソートアルゴリズム
- DNA計算における奇偶転換ソート及びシェアソートアルゴリズム
- DNA計算における奇偶転換ソート及びシェアソートアルゴリズム
- A-017 グリッド環境における完全交換に対するスケジューリングアルゴリズム(A.モデル・アルゴリズム・プログラミング)
- A-008 組み合わせ最適化アルゴリズムに基づく研究室配属システムの開発(A.モデル・アルゴリズム・プログラミング)
- A-003 DNAを用いた0-1整数計画問題の解法(A.モデル・アルゴリズム・プログラミング)
- Procedures for Multiple Input Functions with DNA Strands (Evolutionary Advancement in Fundamental Theories of Computer Science)
- D-1-4 DNA 計算における最大値計算および辞書演算
- 2値画像の重みつき距離変換を行なう並列アルゴリズム
- P-完全問題に対する幾つかの多項式的に加速する並列アルゴリズム
- D-1-7 Polynomially fast parallel algorithms for some P-complete problems
- Cost optimal parallel algorithms for $P$-complete problems (Algorithm Engineering as a New Paradigm)
- D-1-4 抑制性ニューロンを用いたSN Pシステムにおける素因数分解(D-1.コンピュテーション,一般セッション)
- 2分木の平衡分解木を求めるコスト最適な並列アルゴリズム(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- ペイシェンス・ソートおよび最長昇順部分列問題に対するコスト最適な並列アルゴリズム
- スタックを用いた幅優先探索に関する並列アルゴリズム
- 辞書式順極大3和問題に対するBSPモデル上のコスト最適な並列アルゴリズム
- ソート点集合の凸包を求める定数通信ラウンドの並列アルゴリズム
- P完全問題に対するBSPモデル上の並列アルゴリズム
- JSPP '99参加報告(学術会合報告)
- P完全問題の実用的な並列性について
- メッシュ上でユークリッド距離変換を行う並列アルゴリズム
- 濃淡画像の連結成分を求める並列アルゴリズム