Browsing by Author "Hsu, LH"

Now showing 1 - 20 of 52

1-fault tolerant design for token rings
(1998)
Wang, JJ
;
Hung, CN
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper, we present a family of 3-regular, planar, and hamiltonian graphs. Any graph in this family remains hamiltonian if any node or any edge is deleted. Moreover, the diameter of any graph in this family is O(root p) where p is the number of nodes.
A classification of graph capacity functions
(1996-03-01)
Hsu, LH
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
;
Department of Computer Science
Given two graphs G = (V(G), E(G)) and H = (V(H), E(H)), the sum of G and H, G + H, is the disjoint union of G and H. The product of G and H, G x H, is the graph with the vertex set V(G x H) that is the Cartesian product of V(G) and V(H), and two vertices (g(1), h(1)), (g(2), h(2)) are adjacent if and only if [g(1), g(2)] epsilon E(G) and [h(1), h(2)] epsilon E(H). Let G denote the set of all graphs. Given a graph G, the G-matching function, gamma(G), assigns any graph H epsilon G to the maximum integer k such that kG is a subgraph of H. The graph capacity function for G, P-G : G --> R, is defined as P-G(H) = lim(n-->infinity)[gamma(G)(H-n)](1/n), where H-n denotes the n-fold product of H x H x ... x H. Different graphs G may have different graph capacity functions, all of which are increasing. In this paper, we classify all graphs whose capacity functions are additive, multiplicative, and increasing; all graphs whose capacity functions are pseudo-additive, pseudo-multiplicative, and increasing; and all graphs whose capacity functions fall under neither of the above cases. (C) 1996 John Wiley & Sons, Inc.
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 note on the ultimate categorical matching in a graph
(2002-09-28)
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
Let m(G) denote the number of vertices covered by a maximum matching in a graph G. The ultimate categorical matching m*(G) is defined as m*(G) = lim(n-->infinity)m(G(n))(1/n) where the categorical graph product is used. In (Discrete Math. 232 (2001) 1), Albert et al. ask that "Is there a graph G, with at least one edge, such that for all graphs H, m* (G x H) = m * (G)m * (H)?". Actually, m*(G x H) = m*(G)m*(H) holds for any graphs G and H with the previous result of Hsu et al. (Discrete Math. 65 (1987) 53). (C) 2002 Elsevier Science B.V. All rights reserved.
A response to Volgenant's addendum on the most vital edges
(1996-05-01)
Hung, CN
;
Hsu, LH
;
Sung, TY
;
資訊工程學系
;
Department of Computer Science
Adaptive path-based multicast on wormhole-routed hypercubes
(2002)
Wang, CM
;
Hou, YM
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper, we consider path-based multicast on wormhole-routed hypercubes. A minimum set of routing restrictions is used as the base routing algorithm. To correctly perform multicast, we present the natural list to sort the destination nodes. It can be proved to be deadlock-free for both one-port and multi-port systems. Furthermore, it creates only one worm for each multicast. Between each pair of nodes in a multicast path with distance k, on the average, there are at least (k+1)!/2(k) adaptive shortest paths, which is superior to previous works. We also propose a heuristic algorithm to reduce the path length. The simulation result shows that its sustainable throughput is much better than related works. In addition, unicast and broadcast can be treated as degenerated cases and use the same routing algorithm. Therefore, it offers a comprehensive routing solution for communication on hypercubes.
Additive multiplicative increasing functions on nonnegative square matrices and multidigraphs
(2001-09-28)
Chang, CH
;
Chuang, YC
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
It is known that if f is a multiplicative increasing function on N, then either f(n) = 0 for all n is an element of N or f (n) = n(alpha) for some alpha greater than or equal to 0. It is very natural to ask if there are similar results in other algebraic systems. In this paper, we first study the multiplicative increasing functions. over nonnegative square matrices with respect to tensor product and then restrict our result to multidigraphs and loopless multidigraphs. (C) 2001 Elsevier Science B.V. All rights reserved.
Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes
(2003-07-31)
Li, TK
;
Tsai, CH
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to I V(G) I inclusive. It has been shown that Q(n) is bipancyclic if and only if n greater than or equal to 2. In this paper, we improve this result by showing that every edge of Q(n) - E' lies on a cycle of every even length from 4 to V(G) inclusive where E' is a subset of E(Q(n)) with E' less than or equal to n - 2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length I joining any two different vertices x and y of Qn when h (x, y) less than or equal to l less than or equal to V(G) - 1 and l - h (x, y) is even where It (x, y) is the Hamming distance between x and y. (C) 2003 Elsevier Science B.V. All rights reserved.
Broadcasting on wormhole-routed 2D tori with arbitrary size
(1998)
Hou, YM
;
Wang, CM
;
Tsai, MJ
;
Hsu, LH
;
資訊工程學系
For distributed memory parallel computers, broadcast operations are widely used in a variety of applications. In this paper, we propose an efficient algorithm for broadcasting on an all-port wormhole-routed 2D tents with arbitrary size. The underlying network is assumed to support only the dimension-ordered unicast. By taking the advantage of the all-port model and the distance insensitivity of the wormhole routing, the proposed algorithm can greatly reduce the number of message-passing steps. In addition, it can be proved to be depth contention-free. The performance study in this paper clearly shows the advantage of the proposed algorithm.
Brother trees: A family of optimal 1(p)-hamiltonian and 1-edge hamiltonian graphs
(2003-06-15)
Kao, SS
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
In this paper we propose a family of cubic bipartite planar graphs, brother trees, denoted by BT(n) with n greater than or equal to 2. Any BT(n) is hamiltonian. It remains hamiltonian if any edge is deleted. Moreover, it remains hamiltonian when a pair of nodes (one from each partite set) is deleted. These properties are optimal. Furthermore, the number of nodes in BT(n) is 6. 2(n) - 4 and the diameter is 2n + 1. (C) 2003 Elsevier Science B.V. All rights reserved.
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.
Conditional diagnosability measures for large multiprocessor systems
(2005-02-01)
Lai, PL
;
Tan, JJM
;
Chang, CP
;
Hsu, LH
;
資訊工程學系
Diagnosability has played an important role in the reliability of an interconnection network. The classical problem of fault diagnosis is discussed widely and the diagnosability of many well-known networks have been explored. In this paper, we introduce a new measure of diagnosability, called conditional diagnosability, by restricting that any faulty set cannot contain all the neighbors of any vertex in the graph. Based on this requirement, the conditional diagnosability of the n-dimensional hypercube is shown to be 4(n - 2) + 1, which is about four times as large as the classical diagnosability. Besides, we propose some useful conditions for verifying if a system is t-diagnosable and introduce a new concept, called a strongly t-diagnosable system, under the PMC model. Applying these concepts and conditions, we investigate some t-diagnosable networks which are also strongly t-diagnosable.
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.
Cycles in highly faulty hypercubes
(2005)
Yang, MC
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
;
Department of Computer Science
The hypercube Q(n) is one of the most popular networks. In, this paper, we first prove that the n-dimensional hypercube is 2n - 5 conditional fault- bipancyclic. That is, an injured hypercube with up to 2n - 5 faulty links has a cycle of length I for every even 4 <= l <= 2(n) when each node of the hypercube is incident with at least two healthy links. In addition, if a certain node is incident with less than two healthy links, we show that an injured hypercube contains cycles of all even lengths except hamiltonian cycles with up to 2n - 3 faulty links. Furthermore, the above two results are optimal. In conclusion, we find cycles of all possible lengths in injured hypercubes with up to 2n - 5 faulty links under all possible fault distributions.
Diagnosability of t-connected networks and product networks under the comparison diagnosis model
(2004-12-01)
Chang, CP
;
Lai, PL
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
Diagnosability is an important factor in measuring the reliability of an interconnection network, while the (node) connectivity is used to measure the fault tolerance of an interconnection network. We observe that there is a close relationship between the connectivity and the diagnosability. According to our results, a t-regular and t-connected network with at least 2t + 3 nodes is t-diagnosable. Furthermore, the diagnosability of the product networks is also investigated in this work. The product networks, including hypercube, mesh, and tori, comprise very important classes of interconnection networks. Herein, different combinations of t-diagnosable and t-connected are employed to study the diagnosability of the product networks.
Diagnosability of t-connected networks and product networks under the comparison diagnosis model
(2004-12-01)
Chang, CP
;
Lai, PL
;
Tan, JJM
;
Hsu, LH
;
資訊工程學系
Diagnosability is an important factor in measuring the reliability of an interconnection network, while the (node) connectivity is used to measure the fault tolerance of an interconnection network. We observe that there is a close relationship between the connectivity and the diagnosability. According to our results, a t-regular and t-connected network with at least 2t + 3 nodes is t-diagnosable. Furthermore, the diagnosability of the product networks is also investigated in this work. The product networks, including hypercube, mesh, and tori, comprise very important classes of interconnection networks. Herein, different combinations of t-diagnosable and t-connected are employed to study the diagnosability of the product networks.
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.