The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph | Zendy

Janson Svante | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph

Author(s) -

Janson Svante

Publication year - 1995

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.3240070406

Subject(s) - spanning tree , mathematics , combinatorics , discrete mathematics , minimum spanning tree , random graph , graph , random tree , limit (mathematics) , tree (set theory) , computer science , mathematical analysis , motion planning , artificial intelligence , robot

The minimal weight of a spanning tree in a complete graph K n with independent, uniformly distributed random weights on the edges is shown to have an asymptotic normal distribution. The proof uses a functional limit extension of results by Barbour and Pittel on the distribution of the number of tree components of given sizes in a random graph.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research