Efficient generation of graphical partitions
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.
- A note on graphical partitions
- A NOTE ON RANKS AND CONJUGACY OF PARTITIONS
- A recurrence for counting graphical partitions
- scientific article; zbMATH DE number 3646899 (Why is no real title available?)
- scientific article; zbMATH DE number 3169205 (Why is no real title available?)
- On graphical partitions
- Seven criteria for integer sequences being graphic
- The enumeration of graphical partitions
- Graphical basis partitions
- Efficient counting of degree sequences
- An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem
- On maximal graphical partitions that are the nearest to a given graphical partition
- Sufficient conditions for graphicality of bidegree sequences
- scientific article; zbMATH DE number 446400 (Why is no real title available?)
- Very cost effective bipartitions in graphs
- Integer partitions and acyclic directed graphs
- scientific article; zbMATH DE number 1942408 (Why is no real title available?)
- Asymptotic bounds on graphical partitions and partition comparability
- On the strange kinetic aesthetic of rectangular shape partitions
- On maximal graphical partitions
- Methods for the graph realization problem
This page was built for publication: Efficient generation of graphical partitions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1377650)
