Improved Implementation and Analysis of an Algorithm to Count Graphical Partitions

Research output: Contribution to book or proceedingConference articlepeer-review

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.

Original languageEnglish
Title of host publicationProceedings - 2023 International Conference on Computational Science and Computational Intelligence, CSCI 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages420-426
Number of pages7
ISBN (Electronic)9798350361513
DOIs
StatePublished - 2023
Event2023 International Conference on Computational Science and Computational Intelligence, CSCI 2023 - Las Vegas, United States
Duration: Dec 13 2023Dec 15 2023

Publication series

NameProceedings - 2023 International Conference on Computational Science and Computational Intelligence, CSCI 2023

Conference

Conference2023 International Conference on Computational Science and Computational Intelligence, CSCI 2023
Country/TerritoryUnited States
CityLas Vegas
Period12/13/2312/15/23

Scopus Subject Areas

  • Artificial Intelligence
  • Computer Science Applications
  • Computational Mathematics

Keywords

  • counting
  • dynamic programming
  • graphical degree sequence
  • graphical partition
  • recurrence

Fingerprint

Dive into the research topics of 'Improved Implementation and Analysis of an Algorithm to Count Graphical Partitions'. Together they form a unique fingerprint.

Cite this