ソート集合のある分割に対する並列アルゴリズムについて

スポンサーリンク

概要

論文の詳細を見る
本稿では次のような分割問題を考える。要素数nの集合Sがk個の列からなりそれぞれソートされたn/k個の集合として与えられているとき、パラメタh(1/k≤h≤n/k)に対してSを|D_i|=Θ(hk)であり、1≤i<j≤g なる任意の添字iとjに対してD_jのどの要素もD_jのどの要素より大きくないようにg=O(n/(hk))個の部分集合D_1, D_2, ..., D_gに分割する。この分割問題はkとhをうまく設定することにより、マージ、ソートや近似の中間値などを求める問題を含んでおり、また計算幾何学の問題へも応用できる. 本稿では、この分割問題を解く並列アルゴリズムを示す. この並列アルゴリズムはEREW PRAMモデルにおいて O((min{(n/h)*max{log h,1},n*max{log(1/h),1})/(log n)) 個のプロセッサを用いてO(log n)時間で分割問題を解く.
1996-05-29

著者

関連論文

もっと見る

スポンサーリンク