Paper Info
Title
Deterministic Construction of Regular Geometric Graphs with Short Average Distance and Limited Edge Length.
Abstract
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 N x 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.
Year
DOI
Venue
2016
10.1007/978-3-319-49583-5_23
ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, ICA3PP 2016
Keywords
Field
DocType
Regular geometric graphs,Average shortest path length,Cage theory
Graph,Discrete mathematics,Vertex (geometry),Shortest path problem,Spatial network,Computer science,Upper and lower bounds,Parallel computing,Floor plan,Deterministic method,Multiple edges
Conference
Volume
ISSN
Citations 
10048
0302-9743
0
PageRank 
References 
Authors
0.34
11
4
Name
Order
Citations
PageRank
Satoshi Fujita123928.30
Koji Nakano21165118.13
Michihiro Koibuchi372674.68
Ikki Fujiwara412716.00