Browsing by Author "Hwang, FK"

Now showing 1 - 20 of 92

A competitive algorithm to find all defective edges in a graph
(2005-06-15)
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
Consider a graph G (V, E) where a subset D E E is called the set of defective edges. The problem is to identify D with a small number of edge tests, where an edge test takes an arbitrary subset S and asks whether the subgraph G(S) induced by S intersects D (contains a defective edge). Recently, Johann gave an algorithm to find all d defective edges in a graph assuming d D I is known. We give an algorithm with d unknown which requires at most d([log(2) vertical bar E vertical bar] + 4) + 1 tests. The information-theoretic bound, knowing d, is about d log(2) (vertical bar E vertical bar/d). For d fixed, our algorithm is competitive with coefficient 1. (c) 2005 Elsevier B.V. All rights reserved.
A complementary survey on double-loop networks
(2001-07-28)
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
We give a survey on double-loop networks with emphasis on new development since the surveys in 1986, 1991 and 1995. (C) 2001 Elsevier Science B.V. All rights reserved.
A fast reliability-algorithm for the circular consecutive-weighted-k-out-of-n : F system
(1998-12-01)
Chang, JC
;
Chen, RJ
;
Hwang, FK
;
應用數學系
;
資訊工程學系
An O(Tn) algorithm is presented for the circular consecutive-weighted-k-out-of-n:F system, where T less than or equal to min[n, [(k - w(max))/w(min)] + 1]; w(max), w(min) are the maximum, minimum weights of all components. This algorithm is simpler and more efficient than the Wu & Chen O(min[n,k] . n) algorithm. When all weights are unity, this algorithm is simpler than other O(k . n) published algorithms.
A fast reliability-algorithm for the circular consecutive-weighted-k-out-of-n : F system
(1998-12-01)
Chang, JC
;
Chen, RJ
;
Hwang, FK
;
應用數學系
;
資訊工程學系
An O(Tn) algorithm is presented for the circular consecutive-weighted-k-out-of-n:F system, where T less than or equal to min[n, [(k - w(max))/w(min)] + 1]; w(max), w(min) are the maximum, minimum weights of all components. This algorithm is simpler and more efficient than the Wu & Chen O(min[n,k] . n) algorithm. When all weights are unity, this algorithm is simpler than other O(k . n) published algorithms.
A general approach to compute the probabilities of unresolved clones in random pooling designs
(2004)
Hwang, FK
;
Liu, YC
;
應用數學系
;
Department of Applied Mathematics
In this paper, we develop a general approach to compute the probabilities of unresolved clones in random pooling designs. This unified and systematic approach gives better insight for handling the dependency issue among the columns and among the rows. Consequently, we identify some faster computation formulas for four random pooling designs proposed in the literature, and we derive some probability distribution functions of the number of unresolved clones that were not available before.
A general construction for nonblocking crosstalk-free photonic switching networks
(2003-08-01)
Hwang, FK
;
Lin, WD
;
應用數學系
;
Department of Applied Mathematics
The graph representation G(M) of a multistage switching network M is well known. Lea [IEEE Trans Commun 38 (1990), 529-538] observed that link-disjoint paths in M correspond to node-disjoint paths in G(M). He proposed G(M) as a network by treating nodes as crossbars to transfer the node-disjoint property to the crosstalk-free property essential for photonic networks using directional couplers as components. However, such a network has its peculiarities and is not commonly used. In this paper, we will show how to take advantage of this correspondence to construct nonblocking crosstalk-free networks using the vertical stacking method. Our construction simplifies the proofs of many existing results, as well as establishing some new results. (C) 2003 Wiley Periodicals, Inc.
A general construction for nonblocking crosstalk-free photonic switching networks
(2001)
Hwang, FK
;
Lin, WD
;
應用數學系
;
Department of Applied Mathematics
The graph representation G(M) of a multistage network M is well-known. Lea observed that link-disjoint paths in M correspond to node-disjoint paths in G(M). He proposed G(M) as a network by treating nodes as crossbars to transfer the node-disjoint property to the corsstalk-free property essential for photonic net-works using directional couplers as components. However, such a network has its peculiarities and is not the commonly used type. In this paper we use the same principle to establish the crosstalk-free property for the popular Log(2)(N,k,p) network.
A hierarchy of importance indices
(2005-03-01)
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
A new index of component importance
(2001-03-01)
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
Several indices of component importance have been proposed in the literature. The index most relevant to system reliability is the Birnbaum importance, but a comparison between two components is hard to prove and even hard to verify by computation. In this paper we propose a new index which is stronger than the Birnbaum comparison, but always verifiable by computing. In many cases, it could even be easier to prove. We also show the relation of this index with other indices. (C) 2001 Published by Elsevier Science B.V.
A novel use of t-packings to construct d-disjunct matrices
(2006-07-15)
Fu, HL
;
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
A t-packing is an ordered pair (V, P) where V is a nu-set and P is a collection of k-subsets (blocks) of V such that each t-subset of V occurs in at most one block of P. If each t-subset of V occurs in exactly one block of P, then (V, P) is known as a Steiner (t, k, nu)-design. In this paper, we explore a novel use of t-packings to construct d-disjunct matrices. (c) 2006 Elsevier B.V. All rights reserved.
A polynomial time algorithm for shaped partition problems
(1999-11-29)
Hwang, FK
;
Onn, S
;
Rothblum, UG
;
應用數學系
;
Department of Applied Mathematics
We consider the class of shaped partition problems of partitioning n given vectors in d-dimensional criteria space into p parts so as to maximize an arbitrary objective function which is convex on the sum of vectors in each part, subject to arbitrary constraints on the number of elements in each part. This class has broad expressive power and captures NP-hard problems even if either d or p is fixed. In contrast, we show that when both d and p are fixed, the problem can be solved in strongly polynomial time. Our solution method relies on studying the corresponding class of shaped partition polytopes. Such polytopes may have exponentially many vertices and facets even when one of d or p is fixed; however, we show that when both d and p are fixed, the number of vertices of any shaped partition polytope is O(n(d(p2))) and all vertices can be produced in strongly polynomial time.
A simple and direct derivation for the number of noncrossing partitions
(1998-06-01)
Liaw, SC
;
Yeh, HG
;
Hwang, FK
;
Chang, GJ
;
應用數學系
Kreweras considered the problem of counting noncrossing partitions of the set {1, 2, ..., n}, whose elements are arranged into a cycle in its natural order, into p parts of given sizes n(1), n(2), ..., n(p) (but not specifying which part gets which size). He gave a beautiful and surprising result whose proof resorts to a recurrence relation. In this paper we give a direct, entirely bijective, proof starting from the same initial idea as Kreweras' proof.
A survey of nonblocking multicast three-stage Clos networks
(2003-10-01)
Hwang, FK
;
交大名義發表
;
National Chiao Tung University
The author gave a survey on multicast nonblocking multistage interconnection networks in his 1998 book. Here he focuses on the three-stage Clos network and its recursive extensions. Not only will this article bring the literature up to date, but it also will provide some fresh viewpoints to either clarify or simplify some issues.
A survey on multi-loop networks
(2003-04-18)
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
Bermond, Comellas and Hsu gave an excellent survey on multi-loop networks, directed and undirected, in 1995, but only one and half page is on loop networks other than the directed double-loop. Hwang recently gave a substantial survey, but only on the directed double-loop. This survey is a companion of the latter survey by focusing on the other loop networks. (C) 2002 Published by Elsevier Science B.V.
A unifying approach to determine the necessary and sufficient conditions for nonblocking multicast 3-stage Clos networks
(2005-09-01)
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
The 3-stage Clos network is the most-studied switching network. However, exact conditions on the strictly nonblocking multicast three-stage Clos network under various models are difficult to get, due to the messy detail and because each case employs a different argument. Hwang and Liaw made the latest attempt and pointed out errors in previous attempts. However, they made errors, too. In this paper, we propose a unifying approach to study those models systematically (which also applies to some wide-sense nonblocking (WSNB) networks). We also propose a new routing algorithm, and use the unifying approach to derive a necessary and sufficient condition for WSNB.
An almost-linear time and linear space algorithm for the longest common subsequence problem
(2005-05-16)
Guo, JY
;
Hwang, FK
;
應用數學系
;
Department of Applied Mathematics
There are two general approaches to the longest common subsequence problem. The dynamic programming approach takes quadratic time but linear space, while the nondynamic-programming approach takes less time but more space. We propose a new implementation of the latter approach which seems to get the best for both time and space for the DNA application. (c) 2005 Elsevier B.V. All rights reserved.
An efficient algorithm for the reliability of consecutive-k-n networks
(2003-01-01)
Chang, JC
;
Chen, RJ
;
Hwang, FK
;
應用數學系
;
資訊工程學系
A consecutive-k-n network is a generalization of the well-known consecutive-k-out-of-n system, and has many practical applications. This network consists of n + 2 nodes (node 0, the source, nodes 1, 2,..., n, and node n + 1, the target) and directed links from node i to node j (0 less than or equal to i < j less than or equal to n + 1, j - i less than or equal to k). Because all nodes except the source and target, and all links are fallible, the network works if and only if there exists a working path from the source to the target. For the k = 2 case, based on identical node reliabilities and some assumptions on link reliabilities, Chen, Hwang and Li (1993) gave a recursive algorithm for the reliability of the consecutive-2-n network. In this paper we give a closed form equation for the reliability of the general consecutive-k-n network by means of a novel Markov chain method. Based on the equation, we propose an algorithm which is more efficient than other published ones for the reliability of the consecutive-k-n network.
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.
Characterizing the bit permutation networks obtained from the line digraphs of bit permutation networks
(2001-08-01)
Hwang, FK
;
Yen, CH
;
應用數學系
;
Department of Applied Mathematics
A bit permutation network is an s-stage interconnection network composed of d(n-1) d x d crossbar switches in each stage. This class of networks includes most of the multistage interconnection networks. Recently, Chang et al, [Networks 33 (1999), 261-267] showed that an s-stage d-nary bit permutation network N with d(n) inputs (outputs) can be characterized by an (s - 1)-vector (k(1),..., k(s-1)), where k(1) is an element of {1, ..., n - 1}. In this paper, we give a simple (but not trivial) formula to determine the characteristic vector of a new network G(N)(+), which is, approximately, the line digraph of N. We use this formula to obtain relations between some well-studied bit permutation networks. (C) 2001 John Wiley & Sons, Inc.