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 (
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 (
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 (
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 (
ER -