P完全問題の実用的な並列性について
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,いくつかのP完全問題に関して,実用的な並列性があることを示す.まず最初に,多重凸包問題について並列性を示すパラメータを提案する.また,そのパラメーにより問題がP完全である場合の完全性の証明,および,コスト最適な並列アルゴリズムの提案を行う.次に,辞書式順5和問題を取り上げ,辞書式順独立点集合問題からの帰着により,この問題がP完全であることを示す.また,この問題に対するコスト最適な並列アルゴリズムを提案するとともに,アルゴリズムをPVMを使用したPCクラスタ上に実装する.実験結果では,辞書式順5和問題に対して,ほぼ理想的なスピードアップが得られた.
- 一般社団法人情報処理学会の論文
- 1999-09-02
著者
-
藤原 暁宏
九州工業大学大学院情報工学研究院
-
増澤 利光
奈良先端科学技術大学院大学情報科学研究科
-
井上 美智子
奈良先端科学技術大学院大学
-
井上 美智子
奈良先端科学技術大学院大学 情報科学研究科:科学技術振興機構crest
関連論文
- 共有メモリシステムにおける調停木スキップ相互排除アルゴリズム
- BISTにおける高品質遅延故障テストのためのシード選択法(遅延故障テスト,VLSI設計とテスト及び一般)
- D-1-11 非同期膜計算による充足可能性問題とハミルトン路問題の解法(D-1.コンピュテーション,一般セッション)
- C素子スキャンパスを用いた非同期式順序回路に対する完全スキャン設計法(設計/テスト/検証)
- DNA計算における対数時間ソートアルゴリズム
- 再構成アレー上の接頭部和問題について
- 安定後の1故障を考慮したリングでの自己安定相互排除プロトコル
- 安定後の1故障を考慮したリングでの自己安定相互排除プロトコル
- 直交順序を保存する方形の最小面積非交差再配置問題
- 直交順序を保存する矩形の非交差再配置問題について
- 非パイプラインプロセッサの命令レベル自己テストのためのテスト容易化設計(上流DFT,VLSI設計とテスト及び一般)
- 縮退故障とパス遅延故障のためのプロセッサの命令レベル自己テスト法(LSIのテスト・診断技術論文)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- プロセッサ自己テストのためのコントローラ入力時相空間制約(VLSI設計とテスト)
- データフローを考慮したプロセッサ自己テストのためのテンプレート生成(VLSI設計とテスト)
- 分散移動システムにおけるスナップショット・アルゴリズム
- ヘテロジニアスBSPモデル上の2次元データ分割
- 選択問題を解くBSPモデル及びBSP^*モデル上の並列アルゴリズム
- 2値画像上の全最近点を求めるBSPモデル上の並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム(並列・分散)
- 選択問題を解くBSPモデルおよびBSPモデル上の並列アルゴリズム
- 故障推定機能を利用した永久故障に耐性のある自己安定プロトコル
- テスト実行時の温度均一化のためのテストパターン並び替え法(Iddqテスト・温度均一化,VLSI設計とテスト及び一般)
- 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 計算における最大値計算および辞書演算
- RTLパス数最小化のためのリソースバインディング法(スキャンテスト・テスト容易化高位合成,VLSI設計とテスト及び一般)
- 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)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 非同期共有メモリシステムにおける適応型繰り返し改名アルゴリズム
- レジスタ転送レベルデータパスの単一制御可検査性に基づく組込み自己テスト容易化設計法
- 単一制御可検査性に基づくレジスタ転送レベルデータパスの組込み自己テスト容易化設計法
- 単一制御可検査性に基づくレジスタ転送レベルデータパスの組込み自己テスト容易化設計法
- 完全故障検出効率を保証するレジスタ転送レベルでの非スキャンテスト容易化設計法
- 完全故障検出効率を保証するレジスタ転送レベルでの非スキャンテスト容易化設計法
- 完全故障検出効率を保証するレジスタ転送レベルでの非スキャンテスト容易化設計法
- 完全故障検出効率を保証するデータパスの非スキャンテスト容易化設計法 (テストと設計検証論文特集)
- 完全故障検出効率を保証するレジスタ転送レベルデータパスの非スキャンテスト容易化設計法
- 共有メモリマルチプロセッサシステムにおける同期時間最適な無待機時計合せプロトコル(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 線形化可能な分散共有メモリの無待機な実現 (新しいパラダイムとしてのアルゴリズム工学)
- 線形化可能性を保証する分散共有メモリの無待機な実現
- 線形化可能性を保証する共有オブジェクトの無待機な実現
- 共有メモリシステムにおける同期時間最適な自己安定無待機時計合わせプロトコル
- 共有メモリマルチプロセッサシステムにおける同期時間最適な無待機時計合わせプロトコル
- 共有メモリマルチプロセッサシステムにおける同期時間最適な無待機時計合わせプロトコル
- 自律移動ロボット群のための停止故障耐性のある分散型問題解法
- 弱可検査性を考慮したデータパスの高位合成
- D-1-4 抑制性ニューロンを用いたSN Pシステムにおける素因数分解(D-1.コンピュテーション,一般セッション)
- 分散移動システムにおける全域チェックポイントについて
- 高位合成情報を用いたRTLフォールスパス判定(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
- 平衡構造を利用した安全なスキャン設計(スキャンテスト,VLSI設計とテスト及び一般)
- 分散移動システムのための前後関係保存放送プロトコル
- 分散移動システムにおける前後関係保存放送プロトコル
- 完全故障検出効率を保証するレジスタ転送レベルデータパスの非スキャンテスト容易化設計法
- 2連結成分更新問題を解く分散アルゴリズム
- 2分木の平衡分解木を求めるコスト最適な並列アルゴリズム(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- ペイシェンス・ソートおよび最長昇順部分列問題に対するコスト最適な並列アルゴリズム
- スタックを用いた幅優先探索に関する並列アルゴリズム
- 辞書式順極大3和問題に対するBSPモデル上のコスト最適な並列アルゴリズム
- ソート点集合の凸包を求める定数通信ラウンドの並列アルゴリズム
- P完全問題に対するBSPモデル上の並列アルゴリズム
- JSPP '99参加報告(学術会合報告)
- P完全問題の実用的な並列性について
- メッシュ上でユークリッド距離変換を行う並列アルゴリズム
- k-無待機な自己安定k-相互排除プロトコル
- スルー演算を用いた非スキャン方式によるデータパスのテスト容易化設計
- スルー演算を用いた非スキャン方式によるデータパスのテスト容易化設計
- 濃淡画像の連結成分を求める並列アルゴリズム
- マルチアクセスチャネルを考慮した自己安定リーダー選択アルゴリズム
- アドホックネットワークにおけるクラスタ構成法