TY - JOUR
T1 - A new record of graph enumeration enabled by parallel processing
AU - Xu, Zhipeng
AU - Huang, Xiaolong
AU - Jimenez, Fabian
AU - Deng, Yuefan
N1 - Funding Information:
Funding: The research of Z.X. is partially supported by the Special Project on High-Performance Computing of the National Key R&D Program under No.2016YFB0200604.
Funding Information:
Acknowledgments: The authors thank Stony Brook Research Computing and Cyberinfrastructure, and the Institute for Advanced Computational Science at Stony Brook University for access to the high-performance SeaWulf computing system, which was made possible by a $1.4M National Science Foundation grant (#1531492). Also, they thank the National Supercomputing Centers in Jinan and Changsha in China, for computing resources, and M. Meringer of the German Aerospace Center, for technical support regarding GENREG and beneficial suggestions for the manuscript via e-mails.
Funding Information:
The research of Z.X. is partially supported by the Special Project on High-Performance Computing of the National Key R&D Program under No.2016YFB0200604. The authors thank Stony Brook Research Computing and Cyberinfrastructure, and the Institute for Advanced Computational Science at Stony Brook University for access to the high-performance SeaWulf computing system, which was made possible by a $1.4M National Science Foundation grant (#1531492). Also, they thank the National Supercomputing Centers in Jinan and Changsha in China, for computing resources, and M. Meringer of the German Aerospace Center, for technical support regarding GENREG and beneficial suggestions for the manuscript via e-mails.
Publisher Copyright:
© 2019 by the authors.
PY - 2019/12/1
Y1 - 2019/12/1
N2 - Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in the Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of order 23 as 429,668,180,677,439, while discovering several regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The enumeration of 4-regular graphs and the discovery of minimal-ASPL graphs are extremely time consuming. We accomplish them by adapting GENREG, a classical regular graph generator, to three supercomputers with thousands of processor cores.
AB - Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in the Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of order 23 as 429,668,180,677,439, while discovering several regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The enumeration of 4-regular graphs and the discovery of minimal-ASPL graphs are extremely time consuming. We accomplish them by adapting GENREG, a classical regular graph generator, to three supercomputers with thousands of processor cores.
KW - Dynamical scheduling
KW - Parallel computing
KW - Regular graph
UR - http://www.scopus.com/inward/record.url?scp=85079678929&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85079678929&partnerID=8YFLogxK
U2 - 10.3390/math7121214
DO - 10.3390/math7121214
M3 - Article
AN - SCOPUS:85079678929
VL - 7
JO - Mathematics
JF - Mathematics
SN - 2227-7390
IS - 12
ER -