Efficient generation of graphical partitions (Q1377650)

A partition of an even integer \(n\) is called graphical if it is the degree sequence of some simple undirected graph. We are shown how to generate the set, \(G(n)\), of graphical partitions of \(n\). The algorithm is based on a recurrence for \(G(n)\), and the algorithm's efficiency (independent of output) is \(O(|G(n)|)\), which is constant average time per graphical partition. This is the first algorithm shown to achieve such efficiency, and the direct approach differs from earlier `generate and reject' schemes, and the `interval/gap' approach.