@inproceedings{be9730d125694baf89e9cd7cf8b065cb,
title = "Improved Implementation and Analysis of an Algorithm to Count Graphical Partitions",
abstract = "We present a simple and improved implementation of Kohnert's algorithm that computes the number g(n) of graphical partitions of a given even integer n. Two main ingredients of the improvement are: (1) a more precise formula for g(n);(2) an efficient way to compute the four-variate function p(m, k, n, l) introduced by Kohnert. We further show that the algorithm can be easily adapted to compute the g(i) values with all i≤q n for any given n in a single run. A theoretical analysis is given to show that the new implementation to compute all g(i) values for i≤q n is of runtime and space complexity O(n^3). To the best of our knowledge, this is the first analysis to show that g(n) can be computed in O(n 3) time. Experimental evaluations show that our implementation appears to be faster and more space efficient than Kohnert's original implementation.",
keywords = "counting, dynamic programming, graphical degree sequence, graphical partition, recurrence",
author = "Kai Wang",
note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 International Conference on Computational Science and Computational Intelligence, CSCI 2023 ; Conference date: 13-12-2023 Through 15-12-2023",
year = "2023",
doi = "10.1109/CSCI62032.2023.00074",
language = "English",
series = "Proceedings - 2023 International Conference on Computational Science and Computational Intelligence, CSCI 2023",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "420--426",
booktitle = "Proceedings - 2023 International Conference on Computational Science and Computational Intelligence, CSCI 2023",
address = "United States",
}