Skip to content Search
Search our website:

Fast Generation of Unlabelled Free Trees using Weight Sequences

  • Speaker: Paul Brown, Birkbeck, University of London
  • Date: Tuesday, 8 December 2020 from 16:45 to 17:45
  • Location: Virtual, on MS Teams (see link below)
  • Join URL: click here
  • Video URL: click here

We present a new (recursive) algorithm for generating all free trees of order n. Our Python implementation of this algorithm is over four times as fast as the Python implementation of the NetworkX implementation of the well-known WROM algorithm.

For our algorithm, we introduce a new representation for ordered trees, the weight sequence representation. We then use this to construct analogous representations for both rooted trees and free trees, namely the canonical and free weight sequence representations. The main advantage of the weight sequence representation is that, unlike the other representations commonly used, it preserves referential transparency. So, by caching all the rooted trees of small order, we can eliminate many of the recursive calls and greatly reduce the runtime.

Finally, we note that the algorithm can be readily modified to generate the adjacency list and adjacency matrix representations for free trees; the generation times for these are over three times as fast as the corresponding NetworkX implementations of the WROM algorithm.

Presentation slides