Browsing by Author "Tong, LD"

Now showing 1 - 6 of 6

Channel graphs of bit permutation networks
(2001-07-28)
Tong, LD
;
Wang, FK
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
Channel graphs have been widely used in the study of blocking networks. In this paper, we show that a bit pen-nutation network has a unique channel graph if and only if it is connected, and two connected bit pen-nutation networks are isomorphic if and only if their channel graphs are isomorphic. (C) 2001 Elsevier Science B.V. All rights reserved.
Characterizing bit permutation networks
(1998)
Chang, GJ
;
Hwang, FK
;
Tong, LD
;
應用數學系
;
Department of Applied Mathematics
In recent years, many multistage interconnection networks using 2 x 2 switching elements have been proposed for parallel architectures. Typical examples are baseline networks, banyan networks, shuffle-exchange networks and their inverses. As these networks are blocking, such networks with extra stages have also been studied extensively. These include Benes networks and Delta + Delta' networks. Recently, Hwang, Liaw and Yeh studied k-extra-stage networks which is a generalization of the above networks. They also investigated the equivalence issue among some of these networks. In this paper, we study a more general class of networks, which we call (m + 1)-stage d-nary bit permutation networks. We characterize the equivalence of such networks by sequence of positive integers.
Characterizing bit permutation networks
(1999-07-01)
Chang, GJ
;
Hwang, FK
;
Tong, LD
;
應用數學系
;
Department of Applied Mathematics
In recent years, many multistage interconnection networks using 2 x 2 switching elements have been proposed for parallel architectures. Typical examples are baseline networks, banyan networks, shuffle-exchange networks, and their inverses. As these networks are blocking, such networks with extra stages have also been studied extensively. These include Benes networks and Delta + Delta' networks. Recently, Hwang et al, studied k-extra-stage networks, which are a generalization of the above networks. They also investigated the equivalence issue among some of these networks. In this paper, we studied a more general class of networks, which we call (m + 1)-stage d-nary bit permutation networks. We characterize the equivalence of such networks by sequence of positive integers. (C) 1999 John Wiley & Sons, Inc.
Strictly nonblocking three-stage clos networks with some rearrangeable multicast capability
(2003-11-01)
Hwang, FK
;
Liaw, SC
;
Tong, LD
;
應用數學系
;
Department of Applied Mathematics
Hwang and Lin introduced a new nonblocking requirement for 2-cast traffic which imposes different requirements on different types of coexisting calls. The requirement is strictly nonblocking for point-to-point calls among the 2-cast traffic, and is rearrangeable for genuine 2-cast calls. We generalize the 2-cast calls to multicast calls and give a sufficient condition for such networks when the number of multicast calls is upper bounded.
The consecutive-4 digraphs are Hamiltonian
(1999-05-01)
Chang, GJ
;
Hwang, FK
;
Tong, LD
;
應用數學系
;
Department of Applied Mathematics
Du, Hsu, and Hwang conjectured that consecutive-d digraphs are Hamiltonian for d = 3,4. Recently, we gave an infinite class of consecutive-3 digraphs, which are not Hamiltonian. In this article we prove the conjecture for d = 4. (C) 1999 John Wiley & Sons, Inc.
The Hamiltonian property of the consecutive-3 digraph
(1997-06-01)
Chang, GJ
;
Hwang, FK
;
Tong, LD
;
交大名義發表
;
應用數學系
A consecutive-d digraph is a digraph G(d, n, q, r) whose n nodes are labeled by the residues module n and a link from node i to node j exists if and only if j = qi + k (mod n) for some Ic with r less than or equal to k less than or equal to r + d - 1. Consecutive-d digraphs are used as models for many computer networks and multiprocessor systems, in which the existence of a Hamiltonian circuit is important. Conditions for a consecutive-d graph to have a Hamiltonian circuit were known except for gcd(la, d) = 1 and d = 3 Or 4. It was conjectured by Du, Hsu, and Hwang that a consecutive-3 digraph is Hamiltonian. This paper produces several infinite classes of consecutive-3 digraphs which are not (respectively, are) Hamiltonian, thus suggesting that the conjecture needs modification.