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 -