IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v7y2019i12p1214-d296034.html
   My bibliography  Save this article

A New Record of Graph Enumeration Enabled by Parallel Processing

Author

Listed:
  • Zhipeng Xu

    (School of Data and Computer Science, Sun Yat-sen University, Guangzhou, Guangdong 510006, China
    Guangdong Province Key Laboratory of Computational Science, Guangzhou, Guangdong 510275, China
    Department of Applied Mathematics and Statistics, Stony Brook University, Stony Brook, NY 11794, USA)

  • 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)

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.

Suggested Citation

  • Zhipeng Xu & Xiaolong Huang & Fabian Jimenez & Yuefan Deng, 2019. "A New Record of Graph Enumeration Enabled by Parallel Processing," Mathematics, MDPI, vol. 7(12), pages 1-7, December.
    • Handle: RePEc:gam:jmathe:v:7:y:2019:i:12:p:1214-:d:296034
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/7/12/1214/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/7/12/1214/
    Download Restriction: no
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:7:y:2019:i:12:p:1214-:d:296034. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.