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:

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. [9] and , Branching Processes, Springer-Verlag, New York, 1972.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.