著者

中野 浩嗣 オラリウ ステファン

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.100, no.481, pp.25-32, 2000-11-27

---

本論文では、シングルホップの1つのチャネルをもつ無線ネットワーク上にn台のステーションが存在する場合に、リーダ選択を行う省電力確率プロトコルを提案する.提案するプロトコルは、全てのステーションが台数nを知っている場合に、任意のf(f&ge;1)に対して確率1-1/fで、O(log f)時間でリーダ選択を行い、また、どのステーションも高々O(log log f+log f/log n)回の送受信を行う.どのステーションもnを知らない場合、提案するプロトコルは、平均O(log n)時間でリーダ選択を行い、また、確率1-1/fで、O(min((log n)^2+(log f)^2, f^<3/5>olg n))時間動作し、どのステーションも高々O(log n+log f)回の送受信を行う.

著者

林 達也 中野 浩嗣 オラリウステファン

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1996, no.89, pp.23-30, 1996-09-13

参考文献数

19

---

要素数が合計がnのソートされたk個の列をマージして新しいソート列を求める問題をkマージ問題と呼ぶ。本論文では、単純で仕事・時間量が最適な3つのPRAM上のkマージ問題を解くアルゴリズムを示す。まず、EREW?PRAM上で、O(og )時間で仕事量がO( log )のkマージアルゴリズムと、CREW?PRAMとCRCW?PRAM上でO(oglog n+log )時間で仕事量がO( log )のkマージアルゴリズムを示す。また、これらのアルゴリズムが仕事量がO( log )である限り、高速化はできないことを示す。The k-merge problem, given a collection of k,(2〓k〓n), sorted sequences of total length n, asks to merge them into a new sorted sequence. The main contribution of this work is to propose simple and intuitive work-time optimal algorithms for the k-merge problem on three PRAM models. Our k-merge algorithms runs in O(log n) time and performs O(n log k) work on the EREW-PRAM. and in O(loglog n+log k) time and O(n log k) work both on the CREW-PRAM and on the CRCW-PRAM. We also prove that the computing time of these algorithms cannot be improved provided that the amount of work is bounded by O(n log k).