A new record of graph enumeration enabled by parallel processing

Zhipeng Xu; Xiaolong Huang; Fabian Jimenez; Yuefan Deng

doi:10.3390/math7121214

A new record of graph enumeration enabled by parallel processing

Zhipeng Xu, Xiaolong Huang, Fabian Jimenez, Yuefan Deng

Mathematics

Research output: Contribution to journal › Article › peer-review

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.

Original language	English (US)
Journal	Mathematics
Volume	7
Issue number	12
DOIs	https://doi.org/10.3390/math7121214
State	Published - Dec 1 2019

Keywords

Dynamical scheduling
Parallel computing
Regular graph

ASJC Scopus subject areas

Computer Science (miscellaneous)
General Mathematics
Engineering (miscellaneous)

Access to Document

10.3390/math7121214

Cite this

@article{8485a7a8625040d982cb27fb67811ee9,

title = "A new record of graph enumeration enabled by parallel processing",

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 = "Dynamical scheduling, Parallel computing, Regular graph",

author = "Zhipeng Xu and Xiaolong Huang and Fabian Jimenez and Yuefan Deng",

note = "Publisher Copyright: {\textcopyright} 2019 by the authors.",

year = "2019",

month = dec,

day = "1",

doi = "10.3390/math7121214",

language = "English (US)",

volume = "7",

journal = "Mathematics",

issn = "2227-7390",

publisher = "Multidisciplinary Digital Publishing Institute (MDPI)",

number = "12",

}

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

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

SN - 2227-7390

VL - 7

JO - Mathematics

JF - Mathematics

IS - 12

ER -

A new record of graph enumeration enabled by parallel processing

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this