random graphs without cycles

Recall that a closed walk (in a undirected graph) is a cycle if its vertices are pairwise distinct.

Does there exist random constructions of bipartite graphs without cycles with high probability?

-
You might be looking for LERW and UST. –  Did Jun 4 '12 at 10:29

1 Answer

If a graph has no cycles then it is clearly bipartite. Moreover a graph without cycles is a forest. So what you really want is generate trees/forests?

If you're looking to generate random labeled forests/trees then this can be done efficiently using Prüfer sequences. Every such sequence chosen at random gives you a specific labeled tree.

Random non labeled forest are a bit harder to generate.

-