
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Order Adjustment Approach Using Cayley Graphs for the Order/Degree Problem
Teruaki KITASUKA Takayuki MATSUZAKI Masahiro IIDA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E101D
No.12
pp.29082915 Publication Date: 2018/12/01
Online ISSN: 17451361
DOI: 10.1587/transinf.2018PAP0008
Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking) Category: Graph Algorithms Keyword: order/degree problem, Cayley graph, diameter, average shortest path length (ASPL), vertex bisection, vertex injection, vertex removal,
Full Text: PDF(433.5KB) >>Buy this Article
Summary:
The order/degree problem consists of finding the smallest diameter graph for a given order and degree. Such a graph is beneficial for designing lowlatency networks with high performance for massively parallel computers. The average shortest path length (ASPL) of a graph has an influence on latency. In this paper, we propose a novel order adjustment approach. In the proposed approach, we search for Cayley graphs of the given degree that are close to the given order. We then adjust the order of the best Cayley graph to meet the given order. For some order and degree pairs, we explain how to derive the smallest known graphs from the Graph Golf 2016 and 2017 competitions.

