Efficient generation of graphical partitions (Q1377650)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient generation of graphical partitions |
scientific article |
Statements
Efficient generation of graphical partitions (English)
0 references
29 May 1998
0 references
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.
0 references
degree sequences
0 references
integer partitions
0 references