Back to Search
Start Over
A new record of graph enumeration enabled by parallel processing
- Source :
- Mathematics (MDPI), 7(12), 1214(2019)
- Publication Year :
- 2019
-
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 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 serval optimal regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The number of 4-regular graphs and the optimal graphs, extremely time-consuming to calculate, result from a method we adapt from GENREG, a classical regular graph generator, to fit for supercomputers' strengths of using thousands of processor cores.
- Subjects :
- Computer Science - Discrete Mathematics
Mathematics - Combinatorics
05C30, 68R10
Subjects
Details
- Database :
- arXiv
- Journal :
- Mathematics (MDPI), 7(12), 1214(2019)
- Publication Type :
- Report
- Accession number :
- edsarx.1907.12455
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.3390/math7121214