Browsing by Author "Du, DZ"

Now showing 1 - 8 of 8

Interconnecting highways
(1999-04-29)
Du, DZ
;
Hwang, FK
;
Xue, GL
;
應用數學系
;
Department of Applied Mathematics
We present the problem of constructing roads of minimum total length to interconnect n highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a set of optimality conditions for the problem and show how to construct a solution to meet this set of optimality conditions.
Monotone routing in multirate rearrangeable clos networks
(2001-09-01)
Hu, XD
;
Jia, XH
;
Du, DZ
;
Hwang, FK
;
應用數學系
In this paper, we study monotone routing ill the symmetric three-stage Clos network with general bandwidth, and propose a new approach to analyze the multirate rearrangeability. For networks with small size switches. we show that monotone routing is better than the previous methods. (C) 2001 Academic Press.
New construction for transversal design
(2006-05-01)
Du, DZ
;
Hwang, FK
;
Wu, WL
;
Znati, T
;
應用數學系
The study of gene functions requires the development of a DNA library of high quality through much of testing and screening. Pooling design is a mathematical tool to reduce the number of tests for DNA library screening. The transversal design is a special type of pooling design, which is good in implementation. In this paper, we present a new construction for transversal designs. We will also extend our construction to the error-tolerant case.
On greedy construction of connected dominating sets in wireless networks
(2005-12-01)
Li, YS
;
Thai, MT
;
Wang, F
;
Yi, CW
;
Wan, PJ
Since no fixed infrastructure and no centralized management present in wireless networks, a connected dominating set (CDS) of the graph representing the network is widely used as a virtual backbone. Constructing a minimum CDS is NP-hard. In this paper, we propose a new greedy algorithm, called S-MIS, with the help of Steiner tree that can construct a CDS within a factor of 4.8 + ln5 from the optimal solution. We also introduce the distributed version of this algorithm. We prove that the proposed algorithm is better than the current best performance ratio which is 6.8. A simulation is conducted to compare S-MIS with its variation which is rS-MIS. The simulation shows that the sizes of the CDSs generated by S-MIS and rS-MIS are almost the same. Copyright (c) 2005 John Wiley & Sons, Ltd.
On multirate rearrangeable Clos networks
(1998-08-04)
Du, DZ
;
Gao, B
;
Hwang, FK
;
Kim, JH
;
應用數學系
In the multirate switching environment each (connection) request is associated with a bandwidth weight. We consider a three-stage Clos network and assume that each link has a capacity of one (after normalization). The network is rearrangeable if for all possible sets of requests such that each input and output link generates a total weight not exceeding one, there always exists a set of paths, one for each request, such that the sum of weights of all paths going through a link does not exceed the link capacity. The question is to determine the minimum number of center switches which guarantees rearrangeability. We obtain a lower bound of 11n/9 and an upper bound of 41n/16. We then extend the result for the three-stage Clos network to the multistage Clos network. Finally, we propose the weighted version of the edge-coloring problem, which somehow has escaped the literature, associated with our switching network problem.
Optimal consecutive-k-out-of-(2k+1): G cycle
(2001-01-01)
Du, DZ
;
Hwang, FK
;
Jung, Y
;
Ngo, HQ
;
應用數學系
We present a complete proof for the invariant optimal assignment for consecutive-k-out-of-(2k + 1): G cycle, which was proposed by Zuo and Kao in 1990 with an incomplete proof, pointed out recently by Jalali, Hawkes, Cui and Hwang.
Optimal consecutive-k-out-of-n : G cycle for n <= 2k+1
(2002)
Du, DZ
;
Hwang, FK
;
Jia, XH
;
Ngo, HQ
;
應用數學系
A cyclic consecutive-k-out-of-n : G system consists of n components lying on a cycle. Those components are exchangeable but may have different working probabilities. The system works if and only if there are k consecutive components at work. What is the optimal assignment of components for maximizing the reliability of the system? Does the optimal assignment depend on the working probability values of components? For k less than or equal to n less than or equal to 2k+1, Zuo and Kuo in 1990 proposed a solution independent from the working probability values of components, called the invariant optimal assignment. However, their proof is incomplete, pointed out recently by Jalali et al. [ The Optimal Consecutive-k-out-of-n : G Line for n less than or equal to 2k, manuscript, 1999]. We present a complete proof in this paper.
Quadratic integer programming with application to the chaotic mappings of complete multipartite graphs
(2001-09-01)
Fu, HL
;
Shiue, CL
;
Cheng, X
;
Du, DZ
;
Kim, JM
Let a be a permutation of the vertex set V(G) of a connected graph G. Define the total relative displacement of alpha in G by [GRAPHIC] where d(G) (x, y) is the length of the shortest path between x and y in G. Let pi*(G) be the maximum value of delta (alpha)(G) among all permutations of V(G). The permutation which realizes pi*(G) is called a chaotic mapping of G. In this paper, we study the chaotic mappings of complete multipartite graphs. The problem is reduced to a quadratic integer programming problem. We characterize its optimal solution and present an algorithm running in O(n(5) log n) time, where n is the total number of vertices in a complete multipartite graph.