collberg@dna.lth.se (Christian S. Collberg) (04/17/91)
I need to know the average diameter of a DAG of n nodes. Can someone provide a reference? Thanks! -- -------------------------------------------------------------------- Christian.Collberg@dna.lu.se
bdm659@csc.anu.edu.au (04/17/91)
In article <1991Apr17.075727.9539@lth.se>, collberg@dna.lth.se (Christian S. Collberg) writes: > I need to know the average diameter of a DAG of n nodes. > Can someone provide a reference? I presume that by "diameter" you mean the length of the longest path. If each DAG on n nodes (labelled or not) is taken as equally likely, the length of the longest path is asymptotically normally distributed with mean An and variance Bn, where A and B are constants. Approximately A=0.764334 and B=0.145210. Reference: B.D. McKay, On the shape of a random acyclic digraph, Math. Proc. Cambridge Philos. Soc. 106 (1989) 459-465. Another model of a random DAG is as follows: take a DAG with n(n-1)/2 edges (there is essentially only one) and delete each edge with probability 1/2. For this model, the answer to your question is unknown to my knowledge. > Christian.Collberg@dna.lu.se Brendan McKay. Australian National University.