IEICE TRANSACTIONS on Information
Order Adjustment Approach Using Cayley Graphs for the Order/Degree Problem
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 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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E101-D No.12 pp.2908-2915
- Publication Date
- 2018/12/01
- Publicized
- 2018/09/18
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2018PAP0008
- Type of Manuscript
- Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
- Category
- Graph Algorithms
Authors
Teruaki KITASUKA
Hiroshima University
Takayuki MATSUZAKI
Kumamoto University
Masahiro IIDA
Kumamoto University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Teruaki KITASUKA, Takayuki MATSUZAKI, Masahiro IIDA, "Order Adjustment Approach Using Cayley Graphs for the Order/Degree Problem" in IEICE TRANSACTIONS on Information,
vol. E101-D, no. 12, pp. 2908-2915, December 2018, doi: 10.1587/transinf.2018PAP0008.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018PAP0008/_p
Copy
@ARTICLE{e101-d_12_2908,
author={Teruaki KITASUKA, Takayuki MATSUZAKI, Masahiro IIDA, },
journal={IEICE TRANSACTIONS on Information},
title={Order Adjustment Approach Using Cayley Graphs for the Order/Degree Problem},
year={2018},
volume={E101-D},
number={12},
pages={2908-2915},
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.},
keywords={},
doi={10.1587/transinf.2018PAP0008},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Order Adjustment Approach Using Cayley Graphs for the Order/Degree Problem
T2 - IEICE TRANSACTIONS on Information
SP - 2908
EP - 2915
AU - Teruaki KITASUKA
AU - Takayuki MATSUZAKI
AU - Masahiro IIDA
PY - 2018
DO - 10.1587/transinf.2018PAP0008
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E101-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2018
AB - 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.
ER -
English
