TY - JOUR

T1 - An efficient algorithm to find a double-loop network that realizes a given L-shape

AU - Chen, Chiuyuan

AU - Lan, James K.

AU - Tang, Wen Shiang

PY - 2006/8/14

Y1 - 2006/8/14

N2 - Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer N, it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with N nodes. Since the diameter of a double-loop network can be easily computed from its L-shape, one method is to start with a desirable L-shape and then find a double-loop network to realize it. This is a problem discussed by many authors [F. Aguiló, M.A. Fiol, An efficient algorithm to find optimal double loop networks, Discrete Math. 138 (1995) 15-29, R.C. Chan, C.Y. Chen, Z.X. Hong, A simple algorithm to find the steps of double-loop networks, Discrete Appl. Math. 121 (2002) 61-72, C.Y. Chen, F.K. Hwang, The minimum distance diagram of double-loop networks, IEEE Trans. Comput. 49 (2000) 977-979, P. Esqué, F. Aguiló, M.A. Fiol, Double commutative-step diagraphs with minimum diameters, Discrete Math. 114 (1993) 147-157] and it has been open for a long time whether this problem can be solved in O (log N) time. In this paper, we will provide a simple and efficient O (log N)-time algorithm for solving this problem.

AB - Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer N, it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with N nodes. Since the diameter of a double-loop network can be easily computed from its L-shape, one method is to start with a desirable L-shape and then find a double-loop network to realize it. This is a problem discussed by many authors [F. Aguiló, M.A. Fiol, An efficient algorithm to find optimal double loop networks, Discrete Math. 138 (1995) 15-29, R.C. Chan, C.Y. Chen, Z.X. Hong, A simple algorithm to find the steps of double-loop networks, Discrete Appl. Math. 121 (2002) 61-72, C.Y. Chen, F.K. Hwang, The minimum distance diagram of double-loop networks, IEEE Trans. Comput. 49 (2000) 977-979, P. Esqué, F. Aguiló, M.A. Fiol, Double commutative-step diagraphs with minimum diameters, Discrete Math. 114 (1993) 147-157] and it has been open for a long time whether this problem can be solved in O (log N) time. In this paper, we will provide a simple and efficient O (log N)-time algorithm for solving this problem.

KW - Algorithm

KW - Diameter

KW - Double-loop network

KW - L-shape

KW - Local area network

UR - http://www.scopus.com/inward/record.url?scp=33746325501&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2006.01.048

DO - 10.1016/j.tcs.2006.01.048

M3 - Article

AN - SCOPUS:33746325501

VL - 359

SP - 69

EP - 76

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-3

ER -