Depth-First Search Algorithms for Finding a Generalized Moore Graph

Yoshiki Satotani, Norikazu Takahashi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)


Computer networks in data centers are often modeled by undirected regular graphs, and the average shortest path length (ASPL) of the graph is closely related to the data transmission latency. Therefore, finding an undirected regular graph with the minimum ASPL is an important problem for building a low latency network. An undirected regular graph is called a generalized Moore graph (GMG) when its ASPL is identical with the theoretical lower bound. Several methods have been proposed so far to find GMGs with given order and degree. However, they do not make a full use of the properties of GMGs. In this paper, we propose some efficient algorithms for finding a GMG and examine their effectiveness by experiments.

Original languageEnglish
Title of host publicationProceedings of TENCON 2018 - 2018 IEEE Region 10 Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781538654576
Publication statusPublished - Feb 22 2019
Event2018 IEEE Region 10 Conference, TENCON 2018 - Jeju, Korea, Republic of
Duration: Oct 28 2018Oct 31 2018

Publication series

NameIEEE Region 10 Annual International Conference, Proceedings/TENCON
ISSN (Print)2159-3442
ISSN (Electronic)2159-3450


Conference2018 IEEE Region 10 Conference, TENCON 2018
Country/TerritoryKorea, Republic of


  • average shortest path length
  • depth-first search
  • generalized Moore graph
  • network topology
  • optimization

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Depth-First Search Algorithms for Finding a Generalized Moore Graph'. Together they form a unique fingerprint.

Cite this