TY - GEN

T1 - An improved algorithm for counting graphical degree sequences of given length

AU - Wang, Kai

N1 - Publisher Copyright:
© 2019 IEEE.

PY - 2019/12

Y1 - 2019/12

N2 - 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).

AB - 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).

KW - Counting

KW - Graphical degree sequence

KW - Graphical partition

UR - http://www.scopus.com/inward/record.url?scp=85084761121&partnerID=8YFLogxK

U2 - 10.1109/CSCI49370.2019.00088

DO - 10.1109/CSCI49370.2019.00088

M3 - Conference article

AN - SCOPUS:85084761121

T3 - Proceedings - 6th Annual Conference on Computational Science and Computational Intelligence, CSCI 2019

SP - 451

EP - 456

BT - Proceedings - 6th Annual Conference on Computational Science and Computational Intelligence, CSCI 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 6th Annual International Conference on Computational Science and Computational Intelligence, CSCI 2019

Y2 - 5 December 2019 through 7 December 2019

ER -