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

¡@

JENG-JUNG WANG^{1,*}, TUNG-YANG HO^{2}, TING-YI SUNG^{3} AND MING-YI JU^{4}

*
^{1}Department of Information Engineering
I-Shou University
Kaohsiung, 840 Taiwan
^{2}Department of Information Management
Ta Hwa Institute of Technology
Hsinchu, 307 Taiwan
^{3}Institute of Information Science
Academia Sinica
Taipei, 115 Taiwan
^{4}Department 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 (**201303_01.pdf**)

Received February 10, 2012; revised May 3, 2012; accepted July 23, 2012.

Communicated by Hee-Kap Ahn.
^{*} Corresponding author: jjwang@isu.edu.tw.