Deterministic Construction of Regular Geometric Graphs with Short Average Distance and Limited Edge Length

详细信息    查看全文

• 关键词：Regular geometric graphs ; Average shortest path length ; Cage theory
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10048
• 期：1
• 页码：295-309
• 丛书名：Algorithms and Architectures for Parallel Processing
• ISBN：978-3-319-49583-5
• 卷排序：10048

文摘

This paper proposes a deterministic method to construct 5-regular geometric graphs with short average distance under the constraint such that the set of vertices is a subset of \(\mathbb {N}\times \mathbb {N}\) and the length of each edge is at most 4. This problem is motivated by the design of efficient floor plan of parallel computers consisting of a number of computing nodes arranged on a two-dimensional array. In such systems, the degree of vertices is determined by the number of ports of the routers and the edge length is limited by a certain value determined by the cycle time. The goodness of the resulting geometric graph is evaluated by the average shortest path length (ASPL) between vertices which reflects the average communication delay between computing nodes. The idea of the proposed method is to arrange the basic component derived from (3, g)-cage in a two-dimensional manner and to connect adjacent components by parallel edges of length 4 each. The result of numerical calculations shows that the average distance in the resulting graph is close to the lower bound so that the gap to the lower bound is less than 0.98 when the number of vertices is 432000.