著者

中島 孝明 藤原 暁宏

出版者

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

雑誌

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

巻号頁・発行日

vol.101, no.431, pp.1-6, 2001-11-09

参考文献数

9

---

本稿では, 並列化困難な問題として知られているP完全問題の一つである, スタックを用いた幅優先探索の並列性について検証する.まず, 入力グラフの最大次数が3であるようなスタックを用いた幅優先探索もP完全となることを示す.次に, スタックを用いた幅優先探索のP完全性を表す尺度として最長経路距離を導入し, この尺度を用いて, 効率の良い並列アルゴリズムの提案を行う.このアルゴリズムの計算量により, l=O(log^n)の場合, スタックを用いた幅優先探索がクラスNCに属することを示す.ここで, n, lはそれぞれ入力サイズおよび最長経路距離であり, kは正の整数とする.また, このアルゴリズムはl=O(n^ε), 0<ε<1の場合にコスト最適な並列アルゴリズムとなる.