Browsing by Author "Ho, TY"

Now showing 1 - 4 of 4

On mutually independent hamiltonian paths
(2006-04-01)
Teng, YH
;
Tan, JJM
;
Ho, TY
;
Hsu, LH
;
資訊工程學系
Let P-1=< v(1), v(2), v(3),...,v(n)> and P-2=< u(1), u(2), u(3),...,u(n)> be two hamiltonian paths of G. We say that P-1 and P-2 are independent if u(1)=v(1), u(n)=v(n), and u(i)not equal v(i) for 1= 4. We prove that there are at least n-2-(e) over bar mutually independent hamiltonian paths between any pair of distinct vertices of G except n=5 and (e) over bar =1. Assume that G is a graph with the degree sum of any two non-adjacent vertices being at least n+2. Let u and v be any two distinct vertices of G. We prove that there are deg(G)(u)+deg(G)(v)-n mutually independent hamiltonian paths between u and v if (u, v) is an element of E (G) and there are deg(G)(u)+deg(G)(v)-n+2 mutually independent hamiltonian paths between u and v if otherwise. (C) 2005 Elsevier Ltd. All rights reserved.
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.
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.