Skip to content Search
Search our website:

DCS seminar by Dr. Paul Brown on "Fast Generation of Unlabelled Free Trees using Weight Sequences"

Posted: Wednesday, 2 December 2020 00:00

DCS seminar by Dr. Paul Brown on "Fast Generation of Unlabelled Free Trees using Weight Sequences"

The Department of Computer Science and Information Systems announces the first (virtual) DCS Seminar in the academic year 2020/21, which will take place on:

Tuesday, 8 December, 4h45pm - 5h45pm

We are happy to announce the speaker, Paul Brown, Birkbeck, University of London
who will be talking on: "Fast Generation of Unlabelled Free Trees using Weight Sequences"

Abstract:
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.


We will be looking forward to seeing you at the presentation. You can join on MS Teams.