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 and acknowledge you have read our privacy policy.