Premium
The transitive closure of a random digraph
Author(s) -
Karp Richard M.
Publication year - 1990
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240010106
Subject(s) - digraph , transitive closure , combinatorics , mathematics , vertex (graph theory) , transitive relation , closure (psychology) , bounded function , discrete mathematics , graph , mathematical analysis , economics , market economy
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 Θ 2 n vertices, where Θ is the unique root in [0, 1] of the equation 1 − x − e −ex = 0. Nearly all the vertices outside the large strong component line 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 ) 4/3 ), where w(n) is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be Ω( n 2 ) the algorithm presents the transitive closure in the compact form (A × B) U C , where A and B are sets of vertices, and C is a set of arcs.