×

The transitive closure of a random digraph. (English) Zbl 0712.68076

Summary: 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 \(\Theta^ 2n\) vertices, where \(\Theta\) is the unique root in [0,1] of the equation \(1-x-e^{-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)\({}^{4/3})\), where w(n) is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be \(\Omega (n^ 2)\) the algorithm presents the transitive closure in the compact form (A\(\times B)\cup C\), where A and B are sets of vertices, and C is a set of arcs.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C80 Random graphs (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
Full Text: DOI

References:

[1] Palásti, Studia Sci. Math. Hungar. 1 pp 205– (1966)
[2] ”The phase transition in the evolution of random graphs,” manuscript (1988).
[3] Fenner, Combinatorica 2 pp 347– (1988)
[4] Schnorr, SIAM J. Comput. 7 pp 127– (1978)
[5] Random Graphs, Academic, New York, 1985.
[6] Nagaev, Theory of Probability and its Applications pp 98– (1970)
[7] ”Probabilistic Construction of deterministic algorithms: approximating packing integer programs,” Proceedings of the 27th Annual IEEE Symp. on Foundations of Computer Science, 1986, pp. 10–18.
[8] The Theory of Branching Processes, Springer, New York, 1963. · doi:10.1007/978-3-642-51866-9
[9] and , Branching Processes, Springer-Verlag, New York, 1972. · doi:10.1007/978-3-642-65371-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.