Reachability Problems of Random Digraphs
スポンサーリンク
概要
- 論文の詳細を見る
Consider a random digraph G = (V, A), where |V| = n and an arc (u, v) is present in A with probability p (n) independent of the existence of the other arecs. We discuss the expected number of vertices reachable from a vertex, the expected vsize of the transitive closure of G and their related topics based on the properties of reachability, where the reachability from a vertex s to t is defined as the probability that s is reachable to t. Let γ_<n, p(n)> denote the reachability s to t (≠s) in the above random digraph G. (In case of s = t, it requires another definition.) We first present a method of computing the exact value of γ_<n, p(n)> for given n and p (n). Since the computation of γ_<n, p(n)> by this method requires O (n^3) time, we then derive simple upper and lower bounds γ^U_<n, p(n)> and γ^L_<n, p(n)> on γ_<n, p(n)>, respectively, and in addition, we give an upper bound γ^^-_<n, p(n)> on γ^U_<n, p(n)>, which is easier to analyze but is still rather accurate. Then, we discuss the asymptotic behavior of γ^^-_<n, p(n)> and show that, if p (n) = α/ (n-1), lim_<n→∝>γ^^-_<n, p(n)> converges to one of the solutions of the equation 1-x-e^<αx> =0. Furthermore, as for R^^-(n) and T^^-(n), which are upper bounds on the expected number of reachable vertices and the expected size of the transitive closure of G, resp., it turns out that lim_<n→∝>R^^-_n = α/(1-α) if p (n) = α/(n-1) for 0<α<1 ; otherwise either 0 or ∝, and lim_<n→∝>T^^-(n) = α if p (n) = α/(n-1)^2 for α≧0 ; otherwise either 0 or ∝.
- 社団法人電子情報通信学会の論文
- 1998-12-25
著者
-
Uno Yushi
The Department Of Mathematics And Information Sciences College Of Integrated Arts And Sciences Osaka
-
Ibaraki Toshihide
The Department Of Applied Mathematics And Physics Faculty Of Engineering Kyoto University