Efficient generation of graphical partitions
type: Item
instance of: scholarly article
title: Efficient generation of graphical partitions
zbMATH Open document ID: 0889.05011
DOI: 10.1016/S0166-218X(97)00022-X
author: Tiffany M. Barnes
author: Carla D. Savage
published in: Discrete Applied Mathematics
publication date: 1998-05-29T00:00:00Z
full work available at URL: dam
review text: 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.
Mathematics Subject Classification ID: 05A17
zbMATH DE Number: 1109930
zbMATH Keywords: degree sequences
zbMATH Keywords: integer partitions
reviewed by: R. Scurr
MaRDI profile type: Publication
cites work: A NOTE ON RANKS AND CONJUGACY OF PARTITIONS
cites work: A recurrence for counting graphical partitions
cites work: Q3287781
cites work: On graphical partitions
cites work: The enumeration of graphical partitions
cites work: A note on graphical partitions
cites work: Seven criteria for integer sequences being graphic
cites work: Q3205235
OpenAlex ID: W2153659965
description: scientific article; zbMATH DE number 1109930