Nothing Special   »   [go: up one dir, main page]

IEICE Transactions on Information and Systems
Online ISSN : 1745-1361
Print ISSN : 0916-8532
Special Section on Parallel and Distributed Computing and Networking
Order Adjustment Approach Using Cayley Graphs for the Order/Degree Problem
Teruaki KITASUKATakayuki MATSUZAKIMasahiro IIDA
Author information
JOURNAL FREE ACCESS

2018 Volume E101.D Issue 12 Pages 2908-2915

Details
Abstract

The order/degree problem consists of finding the smallest diameter graph for a given order and degree. Such a graph is beneficial for designing low-latency 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.

Content from these authors
© 2018 The Institute of Electronics, Information and Communication Engineers
Previous article Next article
feedback
Top