Improved upper and lower bounds on the optimization of mixed chordal ring networks

• Published in: Information processing letters 2009-06, Vol.109 (13), p.757-762
• Main Authors: Lan, James K., Liu, Victor W., Chen, Chiuyuan
• Format: Article
• Language: English
• Subjects: Algorithmics. Computability. Computer arithmetics; Applied sciences; Calculus of variations and optimal control; Computer science; control theory; systems; Diameter; Double-loop network; Exact sciences and technology; Information processing; Interconnection network; Loop; Mathematical analysis; Mathematics; Miscellaneous; Mixed chordal ring network; Numerical analysis; Numerical analysis. Scientific computation; Numerical methods in mathematical programming, optimization and calculus of variations; Optimization; Parallel processing; Proprietary; Ring; Sciences and techniques of general use; Studies; Theoretical computing
• ISSN: 0020-0190; 1872-6119
• DOI: 10.1016/j.ipl.2009.03.017

Recently, Chen, Hwang and Liu [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3–16] introduced the mixed chordal ring network as a topology for interconnection networks. In particular, they showed that the amount of hardware and the network structure of the mixed chordal ring network are very comparable to the (directed) double-loop network, yet the mixed chordal ring network can achieve a better diameter than the double-loop network. More precisely, the mixed chordal ring network can achieve diameter about 2 N as compared to 3 N for the (directed) double-loop network, where N is the number of nodes in the network. One of the most important questions in interconnection networks is, for a given number of nodes, how to find an optimal network (a network with the smallest diameter) and give the construction of such a network. Chen et al. [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3–16] gave upper and lower bounds for such an optimization problem on the mixed chordal ring network. In this paper, we improve the upper and lower bounds as 2 ⌈ N / 2 ⌉ + 1 and ⌈ 2 N − 3 / 2 ⌉ , respectively. In addition, we correct some deficient contexts in [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3–16].