Browsing by Author "Ngo, Hung Q."
Now showing 1 - 11 of 11
- Results Per Page
- Sort Options
Item A Survey on Combinatorial Group Testing Algorithms with Applications to DNA Library Screening(2000-02-07) Ngo, Hung Q.; Du, Ding-ZhuIn 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.Item 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.Item Error Spreading: A Perception-Driven Approach Orthogonal to Error Handling in Continuous Media Streaming(1999-07-21) Varadarajan, Srivatsan; Ngo, Hung Q.; Srivastava, JaideepWith the growing popularity of the Internet, there is increasing interest in using it for audio and video transmission. Periodic network overloads, leading to bursty packet losses, have always been a key problem for network researchers. In a long-haul, heterogeneous network like the Internet, handling such an error becomes especially difficult. Perceptual studies of audio and video viewing have shown that bursty losses have the most annoying effect on people, and hence are critical issues to be addressed for applications such as Internet phone, video conferencing, distance learning, etc. Classical error handling techniques have focused on applications like FTP, and are geared towards ensuring that the transmission is correct, with no attention to timeliness. For isochronous traffic like audio and video, timeliness is a key criterion, and given the high degree of content redundancy, some loss of content is quite acceptable. In this paper we introduce the concept of error spreading, which is a transformation technique that takes the input sequence of packets (from an audio or video stream) and scrambles its packets before transmission. The packets are unscrambled at the receiving end. The transformation is designed to ensure that bursty losses in the transformed domain get spread all over the sequence in the original domain. Our error spreading idea deals with either cases where the stream has or does not have inter-frame dependencies. Perceptual studies have shown that users are much more tolerant of a uniformly distributed loss of low magnitude. We next describe a continuous media transmission protocol based on this idea. We also show that our protocol can be used complementary to other error handling protocols. Lastly, we validate its performance through a series of experiments and simulations. Keywords: Multimedia, network bursty error, permutation scheme.Item New Bounds on a Hypercube Coloring Problem(1999-03-03) Ngo, Hung Q.; Du, Ding-ZhuOn 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.Item New Constructions of Non-Adaptive and Error-Tolerance Pooling Designs(2000-02-04) Ngo, Hung Q.; Du, Ding-ZhuWe 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.Item On Achieving Lower Consecutive Losses for Continuous Media Streams(1999-02-21) Srivastava, Jaideep; Varadarajan, Srivatsan; Ngo, Hung Q.With the growing popularity of the Internet, there is increasing interest in using it for audio and video transmission. Periodic network overloads, leading to bursty packet losses, have always been a key problem for network researchers. In a long-haul, heterogeneous network like the Internet, handling such an error becomes especially difficult. Perceptual studies of audio and video viewing have shown that bursty losses have the most annoying effect on people, and hence are critical issues to be addressed for applications such as Internet phone, video conferencing, distance learning, etc. Classical error handling techniques have focused on applications like FTP, and are geared towards ensuring that the transmission is correct, with no attention to timeliness. For isochronous traffic like audio and video, timeliness is a key criterion, and given the high degree of content redundancy, some loss of content is quite acceptable. In this paper we introduce the concept of error spreading, which is a transformation technique that takes the input sequence of packets (from an audio or video stream) and scrambles its packet before transmission. The packets are unscrambled at the receiving end. The transformation is designed to ensure that bursty losses in the transformed domain get spread all over the sequence in the original domain. Perceptual studies have shown that users are much more tolerant of a uniformly distributed loss of low magnitude. We next describe a continuous media transmission protocol based on this idea, and validate its performance through an experiment performed on the Internet.Item On the Rearrangeability of Shuffle-Exchange Networks(2000-09-15) Ngo, Hung Q.; Du, Ding-ZhuLet 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 .Item 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.Item 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.Item Statistical Databases(1999-03-09) Srivastava, Jaideep; Ngo, Hung Q.A statistical database management system (SDBMS) is a database management system that can model, store and manipulate data in a manner well suited to the needs of users who want to perform statistical analyses on the data.Statistical databases have some special characteristics and requirements that are not supported by existing commercial database management systems. In this article we provide a general overview of statistical database management, with specific focus on the various technical issues and proposed approaches. By its very nature, the treatment here is brief, and many details have been omitted. References to the original sources are provided, and the reader is invited to refer to them for further details.Item Transmission Fault-Tolerance of Iterated Line Digraphs(2000-11-27) Han, Shituo; Ngo, Hung Q.; Ruan, Lu; Du, Ding-ZhuMany interconnection networks can be constructed with line digraph iterations. In this paper, we will establish a general result on super line-connectivity based on the line digraph iteration which improves and generalizes several existing results in the literature.