Improved Implementation and Analysis of an Algorithm to Count Graphical Partitions

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\leq 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\leq 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$

³
) time. Experimental evaluations show that our implementation appears to be faster and more space efficient than Kohnert's original implementation.