Browsing by Author "Sung, TY"

Now showing 1 - 13 of 13

A family of trivalent 1-hamiltonian graphs with diameter O(log n)
(2001-07-01)
Wang, JJ
;
Sung, TY
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper, we construct a family of graphs denoted by Eye(s) that are 3-regular, 3-connected, planar, hamiltonian, edge hamiltonian, and also minimal 1-hamiltonian. Furthermore, the diameter of Eye(s) is 0(log n), where n is the number of vertices in the Mph and to be precise, n = 6(2(s) - 1) vertices.
A new shortest path routing algorithm and embedding cycles of crossed cube
(1997)
Chang, CP
;
Sung, TY
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
An n-dimensional crossed cube, CQ(n), is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with EFe's algorithm which generates one shortest path in O(n(2)) time, our algorithm can generate more shortest paths in O(n) time. Furthermore, we show that CQ(n) is a pancyclic network and we construct various types of cycles of an arbitrary length at least four.
A response to Volgenant's addendum on the most vital edges
(1996-05-01)
Hung, CN
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
;
Department of Computer Science
Christmas tree: A versatile 1-fault-tolerant design for token rings
(1999-10-29)
Hung, CN
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
;
Department of Computer Science
The token ring topology is required in token passing approach used in distributed operating systems. Fault tolerance is also required in the designs of distributed systems. Note that 1-fault-tolerant design for token rings is equivalent to design of 1-Hamiltonian graphs. This paper introduces a new family of graphs called Christmas tree, denoted by CT(s). The graph CT(s) is a 3-regular, planar, 1-Hamiltonian, and Hamiltonian-connected graph. The number of nodes in CT(s) is 3.2(s) - 2. Its diameter is 1 if s = 1, 3 if s = 2, and 2s if s greater than or equal to 3. (C) 1999 Elsevier Science B.V. All rights reserved.
Construction schemes for fault-tolerant Hamiltonian graphs
(2000-05-01)
Wang, JJ
;
Hung, CN
;
Tan, JJM
;
Hsu, LH
;
Sung, TY
In this paper, we present three construction schemes for fault-tolerant Hamiltonian graphs. We show that applying these construction schemes on fault-tolerant Hamiltonian graphs generates graphs preserving the original Hamiltonicity property. We apply these construction schemes to generate some known families of optimal 1-Hamiltonian graphs in the literature and the Hamiltonicity properties of these graphs are the direct consequence of the construction schemes. In addition, we can use these construction schemes to propose new family of optimal 1-Hamiltonian graphs. (C) 2000 John Wiley & Sons, Inc.
Edge congestion and topological properties of crossed cubes
(2000-01-01)
Chang, CP
;
Sung, TY
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
An n-dimensional crossed cube, CQ(n), is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with Efe's algorithm, which generates one shortest path in O(n(2)) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortest path routing algorithm, we consider a new performance measure of interconnection networks called edge congestion. Using our shortest path routing algorithm and assuming that message exchange between all pairs of vertices is equally probable, we show that the edge congestion of crossed cubes is the same as that of hypercubes. Using the result of edge congestion, we can show that the bisection width of crossed cubes is 2(n-1). We also prove that wide diameter and fault diameter are inverted right perpendicular n/2 inverted left perpendicular + 2. Furthermore, we study embedding of cycles in cross cubes and construct more types than previous work of cycles of length at least four.
Faithful 1-edge fault tolerant graphs
(1997-02-28)
Wang, SY
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
;
Department of Computer Science
A graph G* is 1-edge fault tolerant with respect to a graph G, denoted by 1-EFT(G), if any graph obtained by removing an edge from G* contains G. A 1-EFT(G) graph is said to be optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. Let G(i)* be 1-EFT(G(i)) for i = 1,2. It can be easily verified that the cartesian product graph G(1)* x G(2)* is 1-edge fault tolerant with respect to the cartesian product graph G(1) x G(2). However, G(1)* x G(2)* may contain too many edges; hence it may nor be optimal for many cases. In this paper, we introduce the concept of faithful graph with respect to a given graph, which is proved to be 1-edge fault tolerant. Based on this concept, we present a construction method of the 1-EFT graph for the cartesian product of several graphs. Applying this construction scheme, we can obtain optimal 1-edge fault tolerant graphs with respect to n-dimensional tori C(m(1), m(2),...,m(n)), where m(i) greater than or equal to 4 are even integers for all 1 less than or equal to i less than or equal to n. (C) 1997 Elsevier Science B.V.
Faithful 1-edge fault tolerant graphs
(1997-02-28)
Wang, SY
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
;
Department of Computer Science
A graph G* is 1-edge fault tolerant with respect to a graph G, denoted by 1-EFT(G), if any graph obtained by removing an edge from G* contains G. A 1-EFT(G) graph is said to be optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. Let G(i)* be 1-EFT(G(i)) for i = 1,2. It can be easily verified that the cartesian product graph G(1)* x G(2)* is 1-edge fault tolerant with respect to the cartesian product graph G(1) x G(2). However, G(1)* x G(2)* may contain too many edges; hence it may nor be optimal for many cases. In this paper, we introduce the concept of faithful graph with respect to a given graph, which is proved to be 1-edge fault tolerant. Based on this concept, we present a construction method of the 1-EFT graph for the cartesian product of several graphs. Applying this construction scheme, we can obtain optimal 1-edge fault tolerant graphs with respect to n-dimensional tori C(m(1), m(2),...,m(n)), where m(i) greater than or equal to 4 are even integers for all 1 less than or equal to i less than or equal to n. (C) 1997 Elsevier Science B.V.
On the isomorphism between cyclic-cubes and wrapped butterfly networks
(2000-08-01)
Hung, CN
;
Wang, JJ
;
Sung, TY
;
Hsu, LH
;
資訊工程學系
We show that the cyclic-cubes defined by Ada W.C. Fu and S.C. Chau [1] are isomorphic to k-ary wrapped butterfly networks.
Optimal k-fault-tolerant networks for token rings
(2000-05-01)
Sung, TY
;
Ho, TY
;
Chang, CP
;
Hsu, LH
;
資訊工程學系
Fault-tolerant multiprocessors are widely used in on-line transaction processing. Fault tolerance is also desirable in massively parallel systems that have a relatively high failure probability. Two types of failures in a multiprocessor system are of interest, processor failures and link failures. Most of the previous research in designing optimal fault-tolerant topologies was concentrated on the cases that only processor failures were allowed [1, 2, 4, 6], or the cases that only link failures were allowed [3, 5, 7, 8, 11-15]. In this paper, we discuss the case of a combination of processor failures and link failures for token rings. By "k faults" we mean k-component faults in any combination of processor faults and link faults. Designing an optimal k-fault-tolerant network for token rings is equivalent to constructing an optimal k-hamiltonian graph, where k is a positive integer and corresponds to the number of faults. A graph G is k-hamiltonian if G - F is hamiltonian for any sets F subset of V boolean OR E with F less than or equal to k. An n-node k-hamiltonian graph is optimal if it contains the least number of edges among all n-node k-hamiltonian graphs. In this paper, we construct optimal k-hamiltonian graphs with k = 2 and 3, which are optimal k-fault-tolerant networks with respect to token rings.
The recognition of double Euler trails in series-parallel networks
(1998-08-01)
Ho, TY
;
Sung, TY
;
Hsu, LH
;
Tsai, CH
;
Hwang, JY
Given a series-parallel network (network, for short) N,its dual network N' is given by interchanging the series connection and the parallel connection of network N. We usually use a series-parallel graph to represent a network Let G[N] and G[N'] be graph representations of N and N', respectively. A sequence of edges e(1), e(2),...,e(k) is said to form a common trail on (G[N],G[N']) if it is a trail on both G[N] and G[N']. If a common trail covers all of the edges in G[N] and G[N'], it is called a double Euler trail. However, there are many different graph representations for a network. We say that a network N has a double Euler trail (DET) if there is a common Euler trail for some G[N] and some G[N']. Finding a DET in a network is essential for optimizing the layout area of a complementary CMOS functional cell. Maziasz and Hayes (IEEE Trans. Computer-Aided Design 9 (1990), 708-719) gave a linear time algorithm for solving the layout problem in fixed G[N] and G[N'] and an exponential algorithm for finding the optimal cover in a network without fixing graph representations. In this paper, we study properties of subnetworks of a DET network. According to these properties, we propose an algorithm that automatically generates the rules for composition of trail cover classes. On the basis of these rules, a linear time algorithm for recognizing DET networks is presented. Furthermore, we also give a necessary and sufficient condition for the existence of a double Euler circuit in a network. (C) 1998 Academic Press.
The shuffle-cubes and their generalization
(2001-01-31)
Li, TK
;
Tan, JJM
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
In this paper, we first present a new variation of hypercubes, denoted by SQ(n) .SQ(n) is obtained from Q(n) by changing some links. Sa, is also an n-regular n-connected graph but of diameter about n/4. Then, we present a generalization of Se,. For any positive integer g, we can construct an n-dimensional generalized shuffle-cube with 2(n) vertices which is n-regular and n-connected. However its diameter can be about n/g if we consider g as a constant. (C) 2001 Elsevier Science B.V. All rights reserved.
Transmitting on various network topologies
(1996-03-01)
Ho, TY
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
;
Department of Computer Science
Architectures for interconnection networks can be represented by graphs, while vertices represent processors and edges represent communication links between processors. We use the terms vertices and processors interchangeably. Let G = (V, E) be a graph representing the topology for an interconnection network. Let v(0) be a special vertex outside G, called the host processor, which is connected to each vertex in G. The host processor is the sender or source of the message to be transmitted to all of the vertices in G. In each time unit, the host processor may send an identical message to an arbitrary vertex in G or remain idle. At the same time, each processor in G that has already received the message can send it to all its neighbors in one time unit. A transmitting scheme allowing all processors to receive the message in t time units and requiring the host processor to send the message s times is called a (t, s)-transmitting scheme, where t greater than or equal to s. We call t the transmitting time, and s, the workload of the host processor. We aimed to find an optimal transmitting scheme, i.e., a transmitting scheme such that t is minimized while s is also minimized. In this paper, we present optimal transmitting schemes for linear arrays, rings, complete binary trees, star trees, and (directed) de Bruijn graphs. Furthermore, we present a(t, s)-transmitting scheme for diagonal meshes which are defined slightly different from meshes, and the ratio of t to the optimal transmitting time is approximate to 1.1. (C) 1996 John Wiley & Sons, Inc.