An Improved Algorithm for Counting Graphical Degree Sequences of Given Length
Kai Wang · 2019
We present an improved version of a previous efficient algorithm that computes the number D(n) of zero-free graphical degree sequences of length n. A main ingredient of the improvement lies in a more efficient way to compute the function P(N, k, l, s) of Barnes and Savage. We further show that the algorithm can be easily adapted to compute the D(i) values for all i ≤ n in a single run. Theoretical analysis shows that the new algorithm to compute all D(i) values for i ≤ n is a constant times faster than the previous algorithm to compute a single D(n) value. Experimental evaluations show that the constant of improvement is about 10. The techniques for the improved algorithm can be applied to compute other similar functions that count the number of graphical degree sequences of various classes of graphs of given order or size and that all involve the function P(N, k, l, s).