ペイシェンス・ソートおよび最長昇順部分列問題に対するコスト最適な並列アルゴリズム

概要

論文の詳細を見る
ペイシェンス・ソートおよび最長昇順部分列問題は互いに密接な関係を持つことが知られている問題である.しかし,これら2つの問題が,クラスNC,P完全問題のどちらに属するのかについては知られていない.本稿では,はじめにn個の異なる整数に対するペイシェンス・ソートを解くアルゴリズムを2つ提案する.1つ目のアルゴリズムはEREW PRAMモデル上で動作し,その計算量はp台のプロセッサを用いた場合O(m(n/p+log n))となる.ここで,mはペイシェンス・ソートの解に含まれる降順部分列の数である.2つ目のアルゴリズムはCREW PRAMモデル上で動作し,計算量はO((n log n)/p+m^2 log n/p+m log p)であり,1<p<n/(m^2)の範囲でコスト最適な並列アルゴリズムとなる.最後に,ペイシェンス・ソートの解から同一の入力に対する最長昇順部分列を求める並列アルゴリズムを提案し,そのアルゴリズムの計算量がコスト最適となることを示す.
一般社団法人情報処理学会の論文
2002-05-23