Presentation	1995/6/22 Reachability and the Size of Transitive Closure of a Random Digraph Yushi Uno, Toshihide Ibaraki,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Given 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 arcs, we discuss the expected number of vertices reachable from a given vertex, the expected size of the transitive closure of G, and their related topics based on the properties of reachability. Let γ_ denote the reachability from a vertex s to t (≠s) in the above random digraph G. We firstly present a method of computing the exact value of γ_ for given n and p(n). Since the computation of γ_ by this method requires O(n^3) time, we then derive simple upper and lower bounds γ^U_, respectively, and in addition, we show an upper bound γ^^-_ on γ^U_, which is easy to analyze but still is rather accurate. Then, we discuss the asymptotic behavior of γ^^-_ and show that, if p(n) = α/(n-1), lim_γ^^-_ converges to one of the solutions of the equation l-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, respectively, it turns out that lim_R^^-(n)=α/(1-α) if p(n)=α/(n-1) for 0<α<1 ; otherwise either 0 or ∞, and lim_T^^-(n) = α if p(n)=α/(n-1)^2 for α≥0 ; otherwise either 0 or ∞.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	random digraph / reachability / transitive closure / upper and lower bounds on reachability
Paper #
Date of Issue

Conference Information
Committee	COMP
Conference Date	1995/6/22(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Reachability and the Size of Transitive Closure of a Random Digraph
Sub Title (in English)
Keyword(1)	random digraph
Keyword(2)	reachability
Keyword(3)	transitive closure
Keyword(4)	upper and lower bounds on reachability
1st Author's Name	Yushi Uno
1st Author's Affiliation	Department of Mathematics and Information, College of Integrated Arts and Sciences, University of Osaka Prefecture()
2nd Author's Name	Toshihide Ibaraki
2nd Author's Affiliation	Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University
Date	1995/6/22
Paper #
Volume (vol)	vol.95
Number (no)	126
Page	pp.pp.-
#Pages	10
Date of Issue