Depth-First Search Algorithms for Finding a Generalized Moore Graph

Yoshiki Satotani; Norikazu Takahashi

doi:10.1109/TENCON.2018.8650418

Depth-First Search Algorithms for Finding a Generalized Moore Graph

Yoshiki Satotani, Norikazu Takahashi

School of Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

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 language	English
Title of host publication	Proceedings of TENCON 2018 - 2018 IEEE Region 10 Conference
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	832-837
Number of pages	6
ISBN (Electronic)	9781538654576
DOIs	https://doi.org/10.1109/TENCON.2018.8650418
Publication status	Published - Feb 22 2019
Event	2018 IEEE Region 10 Conference, TENCON 2018 - Jeju, Korea, Republic of Duration: Oct 28 2018 → Oct 31 2018

Publication series

Name	IEEE Region 10 Annual International Conference, Proceedings/TENCON
Volume	2018-October
ISSN (Print)	2159-3442
ISSN (Electronic)	2159-3450

Conference

Conference	2018 IEEE Region 10 Conference, TENCON 2018
Country/Territory	Korea, Republic of
City	Jeju
Period	10/28/18 → 10/31/18

Keywords

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

ASJC Scopus subject areas

Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/TENCON.2018.8650418

Cite this

Satotani, Y., & Takahashi, N. (2019). Depth-First Search Algorithms for Finding a Generalized Moore Graph. In Proceedings of TENCON 2018 - 2018 IEEE Region 10 Conference (pp. 832-837). Article 8650418 (IEEE Region 10 Annual International Conference, Proceedings/TENCON; Vol. 2018-October). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/TENCON.2018.8650418

Depth-First Search Algorithms for Finding a Generalized Moore Graph. / Satotani, Yoshiki; Takahashi, Norikazu.
Proceedings of TENCON 2018 - 2018 IEEE Region 10 Conference. Institute of Electrical and Electronics Engineers Inc., 2019. p. 832-837 8650418 (IEEE Region 10 Annual International Conference, Proceedings/TENCON; Vol. 2018-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Satotani, Y & Takahashi, N 2019, Depth-First Search Algorithms for Finding a Generalized Moore Graph. in Proceedings of TENCON 2018 - 2018 IEEE Region 10 Conference., 8650418, IEEE Region 10 Annual International Conference, Proceedings/TENCON, vol. 2018-October, Institute of Electrical and Electronics Engineers Inc., pp. 832-837, 2018 IEEE Region 10 Conference, TENCON 2018, Jeju, Korea, Republic of, 10/28/18. https://doi.org/10.1109/TENCON.2018.8650418

@inproceedings{03280570b882421f8b0423fee804aa61,

title = "Depth-First Search Algorithms for Finding a Generalized Moore Graph",

abstract = "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.",

keywords = "average shortest path length, depth-first search, generalized Moore graph, network topology, optimization",

author = "Yoshiki Satotani and Norikazu Takahashi",

year = "2019",

month = feb,

day = "22",

doi = "10.1109/TENCON.2018.8650418",

language = "English",

series = "IEEE Region 10 Annual International Conference, Proceedings/TENCON",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "832--837",

booktitle = "Proceedings of TENCON 2018 - 2018 IEEE Region 10 Conference",

note = "2018 IEEE Region 10 Conference, TENCON 2018 ; Conference date: 28-10-2018 Through 31-10-2018",

}

TY - GEN

T1 - Depth-First Search Algorithms for Finding a Generalized Moore Graph

AU - Satotani, Yoshiki

AU - Takahashi, Norikazu

PY - 2019/2/22

Y1 - 2019/2/22

N2 - 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.

AB - 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.

KW - average shortest path length

KW - depth-first search

KW - generalized Moore graph

KW - network topology

KW - optimization

UR - http://www.scopus.com/inward/record.url?scp=85063186980&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85063186980&partnerID=8YFLogxK

U2 - 10.1109/TENCON.2018.8650418

DO - 10.1109/TENCON.2018.8650418

M3 - Conference contribution

AN - SCOPUS:85063186980

T3 - IEEE Region 10 Annual International Conference, Proceedings/TENCON

SP - 832

EP - 837

BT - Proceedings of TENCON 2018 - 2018 IEEE Region 10 Conference

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE Region 10 Conference, TENCON 2018

Y2 - 28 October 2018 through 31 October 2018

ER -

Depth-First Search Algorithms for Finding a Generalized Moore Graph

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this