JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]


Journal of Information Science and Engineering, Vol. 29 No. 2, pp. 193-208


Changing the Diameter in a Diagonal Mesh Network

JENG-JUNG WANG1,*, TUNG-YANG HO2, TING-YI SUNG3 AND MING-YI JU4
1Department of Information Engineering
I-Shou University
Kaohsiung, 840 Taiwan
2Department of Information Management
Ta Hwa Institute of Technology
Hsinchu, 307 Taiwan
3Institute of Information Science
Academia Sinica
Taipei, 115 Taiwan
4Department of Computer Science and Information Engineering
National University of Tainan
Tainan, 700 Taiwan

 

    Communication speed in a parallel and distributed system is related to the diameter of its underlying graph. The diameter of a graph can be affected by the addition or deletion of edges. In this paper we study how the diameter variability problem arises from change of edges of an m x n diagonal mesh, where m and n are not both even integers. We show that the least number of edges whose deletion from an m x n diagonal mesh will increase the diameter is no more than 2, and that the least number of edges whose addition to an m x n diagonal mesh causes the diameter to decrease is no more than m/2 n.

Keywords: diameter, diagonal mesh network, torus, vertex-disjoint path, hypercube

  Retrieve PDF document (JISE_201302_01.pdf)