The Transitive Closure of a Random Digraph
Title | The Transitive Closure of a Random Digraph |
Publication Type | Technical Report |
Year of Publication | 1989 |
Authors | Karp, R. M. |
Other Numbers | 546 |
Abstract | In a random $n$-vertex digraph, each arc is present with probability $p$, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, when $n$ is large and $np$ is equal to a constant $c$ greater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about $ size 9 {(*H} sup 2 n$ vertices, where $ size 9 {(*H}$ is the unique root in $[0,1]$ of the equation $1~-~x~-~e sup -cx ~=~0$. Nearly all the vertices outside the large strong component lie in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected time $O(n)$. For all choices of $n$ and $p$, the expected execution time of the algorithm is $O(w(n)~(n^ log ^n) sup 4/3 )$, where $w(n)$ is an arbitrary non-decreasing unbounded function. To circumvent the fact that the size of the transitive closure may be $(*W (n sup 2 )$ the algorithm presents the transitive closure in the compact form $(A~ times ~B)~(cu~C$, where $A$ and $B$ are sets of vertices, and $C$ is a set of arcs. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1989/tr-89-047.pdf |
Bibliographic Notes | ICSI Technical Report TR-89-047 |
Abbreviated Authors | R. M. Karp |
ICSI Publication Type | Technical Report |