著者

池田 諭 品野 勇治 中森 眞理雄

出版者

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

雑誌

情報処理学会研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.19, pp.17-20, 2002-03-04

---

与えられたグラフG=(V E)が連結か否かを判定することを考える.O(|V|+|E|)のメモリ領域を用いることが出来るならば,O(|V|+|E|)の手間で連結性が判定できることがR.E.Tarjanによって示されている.本論文の目的は,分散システム上で動作する連結性判定分散アルゴリズムを求めることである.本論文では,R.Aleliunas R.M.Karp R.J.Lipton L.Lovaaszおよび C.Rackoff による?RW を用いる手法を取り上げている.そして,簡単な前処理をすることが可能な状況ならば,O(|V|^2 ?log|V|)の手間でほぼ確実に無向グラフの連結性が判定出来ることを示した.また,有向グラフの場合もグラフの直径と次数の上界が分かっているならば同様にして多項式オーダーで判定できることを示した.We consider the reachability problem for directed and undirected graphs. Let G=(V,E) be a directed graph. In [1], R. E. Tarjan has showed the algorithm of O(|V|+|E|) sapce and time complexity. We show a probablistic distributed algorithm for this problem in space O(1) and time O(|V|^2 \log |V|). In this paper,\ we discuss a variant of the algorithm which based on random walk, due to R.Aleliunas, R.M.Karp, R.J.Lipton, L.Lovaasz, and C.Rackoff. We show an improvement of their algorithm from O(|V|^3 log |V|) to O(|V|^2 log |V|) in time helped with a simple preprocessing. In a directed graph,\ we also show their original algorithm run in time O(|V|^2log|V|),\ if the diameter and the degree of the graph is bounded.