Browsing by Author "CHEN, RJ"

Now showing 1 - 15 of 15

A GENETIC ALGORITHM FOR DIVERSITY MINIMIZATION AND ITS PARALLEL IMPLEMENTATION
(1993)
CHEN, RJ
;
MEYER, RR
;
YACKEL, J
;
資訊工程學系
;
Department of Computer Science
AN ALGORITHM FOR COMPUTING THE RELIABILITY OF WEIGHTED-K-OUT-OF-N SYSTEMS
(1994-06-01)
WU, JS
;
CHEN, RJ
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
This paper constructs a new k-out-of-n model, viz, a weighted-k-out-of-n system, and proposes an O(n . k) algorithm for computing its reliability.
AN O(KN) ALGORITHM FOR A CIRCULAR CONSECUTIVE-K-OUT-OF-N-F SYSTEM
(1992-06-01)
WU, JS
;
CHEN, RJ
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
An O(k.n) algorithm is described for evaluating the reliability of a circular consecutive-k-out-of-n:F system.
ANALYSIS OF THE MULTIGROUP METHOD FOR MANIPULATING MULTIPLE STACKS
(1993-02-01)
CHIEN, BC
;
CHEN, RJ
;
YANG, WP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
The multiple stacks problem is that a number of stacks have to be manipulated in a finite continuous memory, simultaneously. Many applications need the support of multiple stacks, e.g., the parallel computing with shared memory. There are two approaches mentioned in [1] for manipulating multiple stacks. In this paper, we present and analyze the Multigroup method which combines the concept of coexisting. By the concept of coexisting, storage sharing in a linear data structure is possible. We show that the new method has better performance than the two previous approaches, and improves the extra manipulating time.
COMPACT EMBEDDING OF BINARY-TREES INTO HYPERCUBES
(1995-04-28)
CHEN, CC
;
CHEN, RJ
;
資訊工程學系
;
Department of Computer Science
COMPETITIVE ANALYSIS OF THE ONLINE ALGORITHMS FOR MULTIPLE STACKS SYSTEMS
(1992-01-01)
CHIEN, BC
;
CHEN, RJ
;
YANG, WP
;
資訊工程學系
;
資訊科學與工程研究所
An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. A competitive algorithm is an on-line algorithm whose cost is bounded by the cost of any other algorithm, even the algorithm is an optimal off-line algorithm, multipling a constant. This paper discusses the algorithms used to manipulate the multiple stacks problem, which is one of the on-line problems. We find the optimal off-line algorithm first, then show that the Knuth's algorithm is not a competitive algorithm, but Garwick's algorithm is competitive when the number Of stacks n is 2. Furthermore the competitive ratio found here is a low bound if the Garwick's algorithm is also & competitive algorithm for n greater-than-or-equal-to 3.
COMPETITIVE ANALYSIS OF THE ONLINE ALGORITHMS FOR MULTIPLE STACKS SYSTEMS
(1992)
CHIEN, BC
;
CHEN, RJ
;
YANG, WP
;
資訊科學與工程研究所
;
Institute of Computer Science and Engineering
An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. A competitive algorithm is an on-line algorithm whose cost is bounded by the cost of any other algorithm, even the algorithm is an optimal off-line algorithm, multipling a constant. This paper discusses the algorithms used to manipulate the multiple stacks problem, which is one of the on-line problems. We find the optimal off-line algorithm first, then show that the Knuth's algorithm is not a competitive algorithm, but Garwick's algorithm is competitive when the number Of stacks n is 2. Furthermore the competitive ratio found here is a low bound if the Garwick's algorithm is also & competitive algorithm for n greater-than-or-equal-to 3.
DISTRIBUTED FAULT-TOLERANT ROUTING IN KAUTZ NETWORKS
(1994-01-01)
CHIANG, WK
;
CHEN, RJ
;
資訊工程學系
;
Department of Computer Science
EFFICIENT ALGORITHM FOR RELIABILITY OF A CIRCULAR CONSECUTIVE-K-OUT-OF-N-F SYSTEM
(1993-03-01)
WU, JS
;
CHEN, RJ
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
The time complexities of previously published algorithms for circular consecutive-k-out-of-n:F system are O(n . k2) and O(n . k). This paper proposes a method to improve upon the original O(n . k2) algorithm and hence derives an O(n . k) algorithm.
EFFICIENT ALGORITHMS FOR K-OUT-OF-N AND CONSECUTIVE-WEIGHTED-K-OUT-OF-N-F SYSTEM
(1994-12-01)
WU, JS
;
CHEN, RJ
;
資訊工程學系
;
Department of Computer Science
A new reliability model, consecutive-weighted-k-out-of-n:F system, is proposed and an O(n) algorithm is provided to evaluate its reliability. An O(n.min(n,k)) algorithm is also presented for the circular case of this model. We design an O(n) parallel algorithm using k processors to compute the reliability of k-out-of-n systems, that achieves linear speedup.
MANIPULATING MULTIPLE STACKS WITH ORDERED-HEAP
(1993-08-15)
CHIEN, BC
;
YANG, WP
;
CHEN, RJ
;
資訊工程學系
;
Department of Computer Science
A new method for manipulating multiple stacks based on dynamic data structure is proposed in this paper. A simple data structure called ordered-heap is developed, in which nodes are preserved as a heap, and kept inorder traversal sequence remains unchanged. By employing ordered-heap to a multiple-stacks environment, it is easy and efficient to simultaneously handle several variable-size stacks in a sequential memory area. Our experiments show that not only the total number of item movements in the proposed method is much smaller than in the previous methods, but also the overhead for maintaining data structure in the proposed method is kept within a reasonable range.
NONASSOCIATIVE PARALLEL PREFIX COMPUTATION
(1992-11-19)
CHEN, RJ
;
HOU, YS
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Associativity of a binary operation allows many applications that are not possible with a non-associative binary operation. We propose a method to transform a binary expression into an associative one and present two related applications.
THE (N,K)-STAR GRAPH - A GENERALIZED STAR GRAPH
(1995-12-08)
CHIANG, WK
;
CHEN, RJ
;
資訊工程學系
;
Department of Computer Science
THE TOWERS OF HANOI PROBLEM WITH CYCLIC PARALLEL MOVES
(1993-04-29)
WU, JS
;
CHEN, RJ
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
This paper discusses a variant of the towers of Hanoi problem with cyclic parallel moves. We propose an algorithm for this problem and show that the algorithm is optimal.
THE TOWERS OF HANOI PROBLEM WITH PARALLEL MOVES
(1992-12-21)
WU, JS
;
CHEN, RJ
;
資訊工程學系
;
Department of Computer Science
This paper proposes a variant of the towers of Hanoi problem allowing parallel moves. An algorithm for this problem is presented and proved to be optimal.