The search functionality is under construction.

The search functionality is under construction.

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 arcs. We discuss the expected number of vertices reachable from a vertex, the expected size 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 γ_{n,p(n)}^{U} and γ_{n,p(n)}^{L} on γ_{n,p(n)}, respectively, and in addition, we give an upper bound _{n,p(n)} on γ_{n,p(n)}^{U}, 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 *G*, resp. , it turns out that lim_{n}*n*) =α/(1-α) if *p*(*n*)=α/(*n*-1) for 0<α<1; otherwise either 0 or _{n}*n*)=α if *p*(*n*)=α/(*n*-1)^{2} for α

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.12 pp.2694-2702

- Publication Date
- 1998/12/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript

- Category
- Graphs and Networks

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yushi UNO, Toshihide IBARAKI, "Reachability Problems of Random Digraphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E81-A, no. 12, pp. 2694-2702, December 1998, doi: .

Abstract: 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 arcs. We discuss the expected number of vertices reachable from a vertex, the expected size 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 γ_{n,p(n)}^{U} and γ_{n,p(n)}^{L} on γ_{n,p(n)}, respectively, and in addition, we give an upper bound _{n,p(n)} on γ_{n,p(n)}^{U}, 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 *G*, resp. , it turns out that lim_{n}*n*) =α/(1-α) if *p*(*n*)=α/(*n*-1) for 0<α<1; otherwise either 0 or _{n}*n*)=α if *p*(*n*)=α/(*n*-1)^{2} for α

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_12_2694/_p

Copy

@ARTICLE{e81-a_12_2694,

author={Yushi UNO, Toshihide IBARAKI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Reachability Problems of Random Digraphs},

year={1998},

volume={E81-A},

number={12},

pages={2694-2702},

abstract={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 arcs. We discuss the expected number of vertices reachable from a vertex, the expected size 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 γ_{n,p(n)}^{U} and γ_{n,p(n)}^{L} on γ_{n,p(n)}, respectively, and in addition, we give an upper bound _{n,p(n)} on γ_{n,p(n)}^{U}, 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 *G*, resp. , it turns out that lim_{n}*n*) =α/(1-α) if *p*(*n*)=α/(*n*-1) for 0<α<1; otherwise either 0 or _{n}*n*)=α if *p*(*n*)=α/(*n*-1)^{2} for α

keywords={},

doi={},

ISSN={},

month={December},}

Copy

TY - JOUR

TI - Reachability Problems of Random Digraphs

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2694

EP - 2702

AU - Yushi UNO

AU - Toshihide IBARAKI

PY - 1998

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E81-A

IS - 12

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - December 1998

AB - 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 arcs. We discuss the expected number of vertices reachable from a vertex, the expected size 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 γ_{n,p(n)}^{U} and γ_{n,p(n)}^{L} on γ_{n,p(n)}, respectively, and in addition, we give an upper bound _{n,p(n)} on γ_{n,p(n)}^{U}, 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 *G*, resp. , it turns out that lim_{n}*n*) =α/(1-α) if *p*(*n*)=α/(*n*-1) for 0<α<1; otherwise either 0 or _{n}*n*)=α if *p*(*n*)=α/(*n*-1)^{2} for α

ER -