Open AccessConstruction and analysis of graph models for multiprocessor interconnection networks
Author(s) -
S. M. Hegde,
Y. M. Saumya
Publication year - 2022
Publication title -
yugoslav journal of operations research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.221
H-Index - 21
eISSN - 1820-743X
pISSN - 0354-0243
DOI - 10.2298/yjor200915017h
Subject(s) - multiprocessing , interconnection , computer science , graph , combinatorics , parallel computing , mathematics , theoretical computer science , computer network
A graph G can serve as a model for the Multiprocessor Interconnection Networks (MINs) in which the vertices represent the processors, while the edges represent connections between processors. This paper presents several graphs that could qualify as models for efficient MINs based on the small values of the graph tightness previously introduced by Cvetkovic and Davidovic in 2008. These graphs are constructed using some well-known and widely used graph operations. The tightness values of these graphs range from O(4?N) to O(?N), where N is the order of the graph under consideration. Also, two new graph tightness values, namely Third type mixed tightness t3(G) and Second type of Structural tightness t4(G) are defined in this paper. It has been shown that these tightness types are easier to calculate than the others for the considered graphs. Moreover, their values are significantly smaller.