I am looking for a simple rejection-free algorithm to uniformly sample random labelled trees (i.e. to generate each of them with the same probability).

One possibility is to generate Prüfer sequences and convert them to trees, but this is not very simple when thought of as a construction procedure. I was wondering is there was a simpler, more direct construction that still guarantees uniform sampling?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.