A New Record of Graph Enumeration Enabled by Parallel Processing

Zhipeng Xu, Xiaolong Huang, Fabian Jimenez and Yuefan Deng
Additional contact information
Zhipeng Xu: School of Data and Computer Science, Sun Yat-sen University, Guangzhou, Guangdong 510006, China
Xiaolong Huang: Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA
Fabian Jimenez: Department of Technological Operations and High Performance Computing, Empresa Publica Yachay, Urcuquí, Imbabura 100115, Ecuador
Yuefan Deng: Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA

Mathematics, 2019, vol. 7, issue 12, 1-7

Abstract: 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.

Keywords: regular graph; parallel computing; dynamical scheduling (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/12/1214/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/12/1214/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:12:p:1214-:d:296034

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().