著者

井上 美智子 萩原 兼一 都倉 信樹

出版者

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

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ = The transactions of the Institute of Electronics, Information and Communication Engineers (ISSN:09151915)

巻号頁・発行日

vol.76, no.7, pp.405-406, 1993-07-25

---

本論文では,非同期の超立方体状ネットワークでの最小重み生成木構成分散問題のメッセージ複雑度の下界がΩ(nlogn)であることを示す(最悪時評価,n:プロセッサ数).上界O(nlogn)は知られているので,この下界はオーダ的には最良である.