Browsing by Author "Du, Ding-Zhu"

Now showing 1 - 20 of 27

A Balanced Term-Weighting Scheme for Effective Document Matching
(2001-02-07) Jung, Yunjae; Park, Haesun; Du, Ding-Zhu
A new weighting scheme for vector space model is presented to improve retrieval performance for an information retrieval system. In addition, a dimension compression method is introduced to reduce the computational cost of the weighting approach. The main idea of this approach is to consider not only occurrence terms but also absent terms in finding similarity patterns among document and query vectors. With a basic information retrieval development system which we are now developing, we evaluate the effect of the balanced weighting scheme and compare it with various combinations of weighting schemes in terms of retrieval performance. The experimental results show that the proposed scheme produces similar recall-precision results to the cosine measure, but more importantly enhances retrieval effectiveness. Since the scheme is based on the cosine measure, it is certain that it has insensitivity to weight variance. The results have convincingly illustrated that the new approach is effective and applicable.
A Distributed Approximation for Minamum Connecting Dominated Sets in Wireless Networks
(2003-05-02) Min, Manki; Lanka, Raghuram; Huang, Xiao; Du, Ding-Zhu
A wireless ad-hoc network is a wireless, multihop network without an infrastructure. And due to the limited resources of hosts in the network, the resource utilization becomes more critical. As a result, construction of virtual backbones in wireless ad-hoc networks gets more attractive. In this paper, we present a distributed approximation scheme for minimum connected dominating sets in unit-disk graphs which can serve as a virtual backbone in the network. Our algorithm has the performance ratio of 7 and the message complexity of $O(n log n)$, which are the best among the schemes in the literature.
A Quadratic Integer Programming with Application in Chaotic Mappings of Complete Multipartite Graphs
(2000-10-02) Fu, Hung-Lin; Shiue, Chin-lin; Cheng, Xiuzhen; Du, Ding-Zhu; Kim, Joon-Mo
Let alpha be a permutation of V(G) of a connected graph G. Define the total relative displacement of alpha in G by where dG(x,y) is the length of the shortest path between x and y in G. Let pi*(G) be the maximum value of deltaalpha(G) among all permutations of V(G) and 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 will reduce to a quadratic integer programming. We characterize its optimal solution and present an algorithm running in O(n5log n) time where n is the total number of vertices in a complete multipartite graph.
A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening
(2000-02-07) Ngo, Hung Q.; Du, Ding-Zhu
In this paper, we give an overview of Combinatorial Group Testing algorithms which are applicable to DNA Library Screening. Our survey focuses on several classes of constructions not previously discussed in the literature, provides a general view on pooling design constructions and poses several open questions arising from this view.
An Effective Term-Weighting Scheme for Information Retrieval
(2000-02-07) Jung, Yunjae; Park, Haesun; Du, Ding-Zhu
The retrieval performance of the information retrieval systems is largely dependent on similarity measures. Furthermore, a term-weighting scheme plays an important role for the similarity measure. In this paper, we investigate existing weighting approaches and similarity measures to propose a new term-weighting scheme supporting the cosine similarity measure to retrieve relevant documents effectively on the basis of vector space model. The new weighting technique considers not only occurrence terms but also absence terms in finding similarity among document vector representations. The consideration of negatively weighted terms resolves the masking by zero problem of the inner product operation. According to the experimental results, the balanced term-weighting scheme performs more effectively especially when the vector space of data collection is relatively dense. Consequently, the balanced weighting scheme promises significant contribution to the relevance effectiveness for the information retrieval systems.
An Extension of DHH-Erdös Conjecture on Cycle-Plus-Triangle Graphs with Application in Switching Networks
(2000-10-20) Du, Ding-Zhu; Ngo, Hung Q.
Consider n disjoint triangles and a cycle on the 3n vertices of the n triangles. In 1986, Du, Hsu, and Hwang conjectured that the union of the n triangles and the cycle has independent number n. Soon later, Paul Erdös improved it to a stronger version that every cycle-plus-triangle graph is 3-colorable. This conjecture was proven by H. Fleischner and M. Stiebitz. In this note, we want to give an extension of the above conjecture with an application in switching networks.
Approximation Solutions for the Resource Management Problem Using the General Cover Problem
(2001-12-13) Cardei, Mihaela; MacCallum, David; Chen, Sai; Cardei, Ionut; Du, Ding-Zhu
Time-critical applications and multimedia systems require a mechanism to arbitrate access to shared resources. Resource Management systems provide the necessary services to applications for admission control and adaptation. This paper defines a model for the Resource Management Problemand describes two near-optimal approximation methods for criticality-based selection scheduling of competing applications. The resource management allocation scheme is designed to follow a set of goals. In this paper we focus on maximizing the number of higher-criticality sessions admitted, where a session is an instance of an application executing on a system, using a set of resources, such as CPU, memory and disk IO. First we reduce the Resource Management Problem to the General Cover Problem and thenpresent two approximation solutions with their performance ratio. First solution uses a greedy algorithm and the second one a linear programming algorithm.
Connected Dominating Sets in Wireless Networks with Different Transmission Ranges
(2005-11-21) Thai, My T.; Wang, Feng; Liu, Dan; Zhu, Shiwei; Du, Ding-Zhu
Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed as the virtual backbone. The CDS of a graph representing a network has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which each node has the same transmission range. However, in practice, the transmission ranges of all nodes are not necessary equal. In this paper, we model a network as a disk graph and introduce the CDS problem in disk graphs. We present three constant approximation algorithms to obtain a minimum CDS of a given network. These algorithms can be implemented as distributed algorithms. Furthermore, we show the size relationship between a maximal independent set and a CDS as well as the bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.
Fault Tolerant Topology Control for All-to-One and One-to-All Communication in Wireless Networks
(2005-11-29) Wang, Feng; Thai, My T.; Li, Yingshu; Du, Ding-Zhu
This paper introduces the problem of fault tolerant topology control for all-to-one and one-to-all communication in static wireless networks with asymmetric wireless links. This problem is important in both theoretical and practical aspects. We investigate two approaches, namely minimum weight based approach and nearest neighbor augmentation approach,to address this problem. Specifically, for each approach, we propose three algorithms for three interpretations of the problem: 1) construct k-node disjoint paths from every node to a specific root node, 2) construct k-node disjoint paths from the root node to every other node, 3) construct k-node disjoint paths from the root node to every other node and also from every node to the root node. Furthermore, we give theoretical analysis for all six algorithms. Among other results, we show that the minimum weight based approach has a k-approximation algorithm for all-to-one fault tolerant topology control where k is the number of disjoint paths. When k=1, this approach solves the minimum power all-to-one 1-connected topology control problem. Through extensive simulations, we demonstrate that minimum weight based approach performs better for the first two interpretations and the augmentation based approach performs better for the third interpretation. To the best of our knowledge, this paper is the first to study the fault tolerant topology control for all-to-one and one-to-all communication in asymmetric static wireless networks, and also is the first to demonstrate that the minimum power all-to-one 1-connected topology control problem has an optimal solution.
Maximal Independent Set and Minimum Connected Dominating Set in Unit Disk Graphs
(2004-12-13) WuLi, Wei; Du, Hongwei; Jia, Xiaohua; Li, Yingshu; Huang, Scott C.-H.; Du, Ding-Zhu
In ad hoc wireless networks, the connected dominating set can be used as a virtual backbone to improve the performance. Many constructions for approximating the minimum connected dominating set are based on construction of maximal independent set. The relation between the size mis(G) of a maximum independent set and the size cds(G) of minimum connected dominating set in the same graph G plays an important role in establishing the performance ratio of those approximation algorithms. Previously, it is known that mis(G)<=4*cds(G)+1 for all unit disk graph G. In this paper, we improve it by showing mis(G)<=3.8*cds(G)+1.2.
New Bounds on a Hypercube Coloring Problem
(1999-03-03) Ngo, Hung Q.; Du, Ding-Zhu
On studying the scalability of optical networks, one problem arising is to color the vertices of the $n$-cube with as few colors as possible such that any two vertices whose Hamming distance is at most $k$ are colored differently. Determining the exact value of $chi_k(n)$, the minimum number of colors needed, is a difficult problem. In this paper, we improve the lower and upper bounds of $chi_k(n)$ and indicate the connection of this coloring problemto linear codes.
New Constructions of Non-Adaptive and Error-Tolerance Pooling Designs
(2000-02-04) Ngo, Hung Q.; Du, Ding-Zhu
We propose two new classes of non-adaptive pooling designs. The first one is guaranteed to be d-error-detecting and thus [d/2]-error-correcting given any positive integer d. Also, this construction induces a construction of a binary code with minimum Hamming distance at least 2d+2. The second design is the q-analogue of a known construction on d-disjunct matrices.
New Constructions On Broadcast Encryption and Key Pre-Distribution Schemes
(2004-06-24) Huang, Scott C.-H.; Du, Ding-Zhu
This paper presents various new techniques on secure group communication schemes. We present a new broadcast encryption scheme Arachne, being particularly efficient in multiple revocation, and a node-based key pre-distribution scheme, remedying the key overlapping problem of pool-based schemes. Starting with a detailed analysis on broadcast encryption and group key distribution schemes, we discuss the influence of emph{join} as well as the feasibility of including it in broadcast encryption schemes by means of performing full updating or overprovisioning.
On Greedy Construction of Connected Dominating Sets in Wireless Networks
(2004-12-16) Li, Yingshu; Thai, My T.; Wang, Feng; Yi, Chih-Wei; Wan, Pengjun; Du, Ding-Zhu
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 the virtual backbone and plays an important role in the network. Constructing a minimum CDS is NP-hard. Many CDS construction algorithms have been designed. 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. The theoretical proof shows that our 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.
On the Construction of 2-Connected Virtual Backbones in Wireless Networks
(2005-11-29) Wang, Feng; Thai, My T.; Du, Ding-Zhu
Virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem in ad hoc networks. Since the nodes in the virtual backbone need to carry other node's traffic, and node and link failure are inherent in wireless networks, it is desirable that the virtual backbone is fault tolerant. In this paper, we propose a new algorithm called Connecting Dominating Set Augmentation (CDSA) to construct a 2-connected virtual backbone which can resist the failure of one wireless node. We prove that CDSA has guaranteed quality, because the size of the CDSA constructed 2-connected backbone is within a constant factor of the optimal 2-connected virtual backbone size. Through extensive simulations, we demonstrate that CDSA can improve the fault tolerance of virtual backbone with marginal overhead.
On the Construction of a Strongly Connected Broadcast Arborescence with Bounded Transmission Delay
(2004-12-13) Li, Yingshu; Thai, My T.; Wang, Feng; Du, Ding-Zhu
Energy conservation is an important concern in wireless networks. Many scenarios for constructing a broadcast tree with minimum energy consumption and other goals have been developed. However, no previous research work considers the total energy consumption and transmission delays of the broadcast tree simultaneously. In this paper, based on (alpha, beta)-tree, a novel concept to wireless networks, we define a new Strongly Connected Broadcast Arborescence with Bounded Transmission Delay (SBAT) Problem and design the strongly connected broadcast arborescence (SBA) construction algorithm with linear running time to construct a strongly connected broadcast tree with bounded cost, i.e., total energy, while satisfying the constraint that the transmission delay between the source and other hosts are also bounded. We also propose the distributed version of the SBA algorithm. The theoretical analysis and simulation results show that the SBA algorithm gives a proper solution to the SBAT problem.
On the Rearrangeability of Shuffle-Exchange Networks
(2000-09-15) Ngo, Hung Q.; Du, Ding-Zhu
Let m(n) be the minimum positive integer k so that the Shuffle-Exchange network with k stages, N = 2n inputs and N outputs is rearrangeable. Beneš conjectured that m(n)=2n-1 . The best bounds known so far are 2n-1 <= m(n) <= 3n-4 . In this paper, we verify Beneš conjecture for n=4 , and use this result to show that m(n) <= 3n-5 .
Optimal Consecutive-k-out-of-(2k+1): G Cycle
(2000-10-02) Du, Ding-Zhu; Hwang, Frank K.; Jung, Yunjae; Ngo, Hung Q.
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
(2000-10-02) Du, Ding-Zhu; Hwang, Frank K.; Jia, Xiaohua; Ngo, Hung Q.
We present a complete proof for the invariant optimal assignment for consecutive-k-out-of-n: G Cycle for k , which was proposed by Zuo and Kao in 1990 with an incomplete proof, pointed out recently by Jalali, Hawkes, Cui, and Hwang.
Optimal Relay Location for Resource-Limited Energy-Efficient Wireless Communication
(2002-03-26) Cardei, Ionut; Cardei, Mihaela; Wang, Lusheng; Xu, Baogang; Du, Ding-Zhu
In the design of wireless networks, techniques for improving energy efficiency and extending network lifetime have great importance, particularly for defense and civil/rescue applications where resupplying transmitters with new batteries is not feasible. In this paper we study a method for improving the lifetime of wireless networks by minimizing the length of the longest edge in the interconnecting tree with deploying additional relay nodes.Let P={p1, ..., pn} be a set of n terminals in the Euclideanplane. For a positive integer k, the bottleneck Steinertree problem (BSTP) asks to find a Steiner tree with atmost k Steiner points such that the length of the longest edge in the tree is minimized. We give a ratio - sqrt(3) + e polynomial time approximation algorithm for BSTP, where e is an arbitrary positive number.Keywords:wireless networks, power efficient, approximation algorithms, Steiner tree, bottleneck Steiner tree.

University Digital Conservancy

Browse by Author

Browsing by Author "Du, Ding-Zhu"