My research interests are centered on the Combinatorial Optimization and its connection to Computer Networks and Computational Biology. More specifically, the focus of my research is to design and analyze efficient algorithms (mainly approximation algorithms) for many computationally hard problems in Wireless Sensor Networks, Wireless Networks, and Computational Biology. The following are some of my recent research work.

• Motivations: Pooling designs (mathematically called Group Testing) are used in DNA library screening to efficiently distinguish positive clones from negative clones, which are of fundamental importance in studying gene functions. Due to the large number of testing and screening, it is desirable to obtain a pool design with the minimum number of tests. More complicated, biological experiments usually contain errors and in some applications, there is a third category of clones called "inhibitors" whose effect is to neutralize positives. Thus pooling designs must be able to handle the fault-tolerance and inhibitors.
• Objectives: Construct pooling design using d-disjunct matrix  for both classical model and complex. Devise new algorithms for non-unique probes.
• Selected Publications:
  • My T. Thai, David MacCallum, Ping Deng, and Weili Wu, Decoding Algorithms in Pooling Designs with Inhibitors and Error-Tolerance, IJBRA, 2006
  • Hong Gao, F.K. Hwang, My T. Thai, Weili Wu, and Taieb Znati, Construction of d(H)-Disjunt Matrix for Group Testing in Hypergraphs, J. of Combinatorial Optimization, to appear, 2006
  • Yingshu Li, My T. Thai, Zhen Liu, and Weili Wu, Protein-Protein Interaction and Group Testing in Bipartite Graphs, International Journal of Bioinformatics Research and Applications (IJBRA), vol. 1, no. 4, pp. 414-419, 2005.

• Motivations: Recent advances in post-genomic biology are enabling us to investigate and re-construct the precise gene interaction networks. Inferring genetic networks from a large-scale expression data is very important to understand the underlying biological systems. Because of the large-scale data, techniques to process a raw expression data, i.e., clustering data, for reconstructing genetic networks and models for inferring genetic networks are important.
• Objectives: Devise new graph models for regulatory networks and protein-protein interaction networks, devise a new graph model for clustering problem in biology
• Selected Publications:
  • My T. Thai, Zhipeng Cai, and Ding-Zhu Du, Genetic Networks: Processing Data, Regulatory Network Modeling, and their Analysis, special issue of J. Optimization Methods and Software on Optimization and Data Mining Techniques in Biomedicine, to appear, 2006

• Motivations: With recent advances in technology, applying and using Wireless Sensor Networks (WSN) in our daily lives in the next decades are no longer a dream, but a reality. An important problem in WSN is the sensor coverage problem, which reflects the quality of service that can be provided by a particular sensor network. However, sensor nodes are battery powered and have a limited weight. Thus it is critical to design energy efficient algorithms to prolong network lifetime while guaranteeing the complete coverage.
• Objectives: Model the problem, study their characteristics, devise the approximation algorithms with good performance ratio and practical, i.e., distributed and localized algorithms, and study their complexities
• Selected Publications:
  • My T. Thai, Feng Wang, and Ding-Zhu Du, Coverage Problems in Wireless Sensor Networks: Designs and Analysis, International Journal of Sensor Networks, special issue on Coverage Problems in Sensor Networks, accepted, 2005
  • Mihaela Cardei, My T. Thai, Yingshu Li, and Weili Wu, Energy-Efficient Target Coverage in Wireless Sensor Networks, in Proceedings of the 24^th conference of the IEEE Communications Society (INFOCOM 2005), March 2005.
  • My T. Thai, Yingshu Li, Feng Wang, and Ding-Zhu Du, O(log n)-Localized Algorithms on the Coverage Problem in Wireless Sensor Networks, submitted to IEEE Transactions on Parallel and Distributed Systems, 2005.
  • My T. Thai, Yingshu Li, Feng Wang, and Ding-Zhu Du, Minimum Coverage Breach and Maximum Network Lifetime in Wireless Sensor Networks, submitted to IEEE Transactions on Wireless Communications, 2005

• Motivations: Since there is no fixed or pre-defined infrastructures in wireless ad hoc networks, it is important to construct the virtual backbone. With the help of the virtual backbone, communication in networks, i.e., broadcasts and routing, and its maintenance are simpler and easier.
• Objectives: Model the virtual backbone as the Connected Dominating Set (CDS) problem, study the CDS problem in different models of networks: Unit Disk Graphs, Disk Graphs, and Directed Graphs, design and analyze the efficient approximation algorithms for this NP-hard problem.
• Selected Publications:
  • My T. Thai, Feng Wang, Dan Liu, Shiwei Zhu, and Ding-Zhu Du, Connected Dominating Sets in Wireless Networks with Different Transmission Ranges, IEEE Transactions on Mobile Computing, accepted with minor revisions, 2006
  • Ding-Zhu Du, My T. Thai, Yingshu Li, Dan Liu, and Shiwei Zhu, Strongly Connected Dominating Sets in Wireless Sensor Networks with Unidirectional Links, in  Proceedings of APWEB, Lecture Notes in Computer Science, Springer, 2006.
  • Yingshu Li, My T. Thai, Feng Wang, Chih-Wei Yi, Pengjun Wan, and Ding-Zhu Du, On Greedy Construction of Connected Dominating Sets in Wireless Networks, special issue of Wireless Communications and Mobile Computing (WCMC), vol. 5, no. 88, pp. 927-932, 2005.
  • My T. Thai and Ding-Zhu Du, Connected Dominating Sets in Disk Graphs with Bidirectional Links, IEEE Communications Letters, vol. 10, no. 3, pp. 138-140, March 2006.

• Motivations: In most cases, wireless networks are deployed under a harsh environment. Thus it is not surprising that wireless nodes and links experience frequent failures, resulting in significant impact on the performance and reliability of networks and upper level applications. Therefore, how to ensure fault tolerance is a very important issue in wireless networks. One of the traditional fault tolerance techniques is to construct k-Vertex/Edge connected topology.
• Objectives: Investigate the k-Vertex/Edge connected topology, devise a new model for fault tolerance, and construct and analyze approximation algorithms on the new model
• Selected Publications:
  • Feng Wang, My T. Thai, Yingshu Li, and Ding-Zhu Du, Fault Tolerant Topology Control for All-to-One and One-to-All Communication in Wireless Networks, IEEE Transaction on Mobile Computing, accepted with minor revisions, 2006.
  • Feng Wang, My T. Thai, and Ding-Zhu Du, 2-Connected Virtual Backbone in Wireless Networks, accepted with revisions, IEEE Transactions on Wireless Communications, 2006.

• Motivations: Broadcasts and multicasts are two main methods of communications in wireless networks. As mentioned, energy efficiency is one of the most concerned factors in wireless networks among many performance metrics. It is thus important to devise a new broadcast/multicast protocol to minimize the energy consumption. This problem is well-known to be NP-complete.
• Objectives: Model the problem, devise approximation algorithms taking Hitch-hiking into consideration, not only minimize the energy consumption but also bound the transmission delay.
• Selected Publications:
  • My T. Thai, Yingshu Li, and Ding-Zhu Du, A Combination of Wireless Multicast Advantage and Hitch-hiking, IEEE Communications Letters, vol. 9, no. 12, December 2005.
  • Yingshu Li, My T. Thai, Feng Wang, and Ding-Zhu Du, On the Construction of a Strongly Connected Broadcast Arborescence with Bounded Transmission Delay, IEEE Transactions on Mobile Computing, accepted with a minor revision, 2005.