[net.ai] MST distributions

cross%lsu.csnet@csnet-relay.arpa (10/02/84)

From:  "George R. Cross" <cross%lsu.csnet@csnet-relay.arpa>

           [Forwarded from the SRI bboard by Laws@SRI-AI.]

I am interested in references to the following problem:

Suppose we have n-points uniformly distributed in a subset S contained in
p-dimensional Euclidean space R^p:

1.What is the distribution of the largest length of the Minimum
Spanning Tree (MST) over the n-points?  Assume Euclidean distance is
used to define the edge weights.

2.What is the distribution of the length of edges in the MST?

3.What is the distribution of the size of the maximal clique?

Asymptotic results or expected values of these quantities would be
interesting also.  We expect to make use of this information in
cluster algorithms.

Thanks,
        George Cross
        Computer Science
        Louisiana State University

        CSNET: cross%lsu@csnet-relay