マージングネットワークの下界について
スポンサーリンク
概要
- 論文の詳細を見る
(m, n)-マージングネットワークにおける最小比較交換器数をM(m, n)で表す. 本論文ではM(4, 5)=12を証明する. 証明では12未満の比較交換器数からなる(4, 5)-マージングネットワークの存在を仮定し矛盾を導く. 次にM(4, 6)=14であることをコンピュータによる膨大な計算を含めて示す. この計算は基本的には木探索であるが, バックトラックの枝掛りをいかに多くするかが大きな作業である. 最後にM(4, 8)=17を証明する.
- 社団法人電子情報通信学会の論文
- 1997-08-25
著者
関連論文
- D-1-2 「ストーンヘンジ」の先手必勝性と一般化ストーンへンジのPSPACE完全性(D-1. コンピュテーション,一般セッション)
- 一般化詰将棋問題の指数時間完全性
- 一般化詰将棋問題の指数時間完全性について
- D-1-1 一般化美術館問題のNP完全性(D-1.コンピュテーション,一般講演)
- 単一2負項を加えたホーン関数
- 単一2負項を加えたホーン関数
- 一般化ブロックパズルのPSPACE完全性の別証明 (計算機科学基礎理論の新展開)
- LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集の発行にあたって(LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
- LAシンポジウム(情報基礎理論ワークショップ)論文小特集の発行にあたって(和文論文誌D-I・英文論文誌E-D合同)
- T(G)を計算する新しいアルゴリズム
- T(G)を計算する新しいアルゴリズム
- (4,7)-、(5,6)-マージングネットワークの最小比較器数のコンピュータによる計算 (離散的アルゴリズムと計算量)
- (4, 7)-マージングネットワークと(5, 6)-マージングネットワークの最小比較器数について
- マージングネットワークの下界について
- マージングネットワークの下界の計算について
- マージングネットワークにおけるある下界について(計算量理論の諸相 : その基礎的研究)
- n×n盤面上の将棋の指数時間完全性について