Downloadable Papers

1. Algorithms for Reticulate Networks of Multiple Phylogenetic Trees. IEEE/ACM Transactions on Computational Biology and Bioinformatics, to appear.
2. Mutation Region Detection for Closely Related Individuals without a Known Pedigree. IEEE/ACM Transactions on Computational Biology and Bioinformatics, to appear. (Joint with W. Ma, Y. Yang, and L. Wang.)
3. A Three-String Approach to the Closest String Problem. Journal of Computer and System Sciences. Presented at CoCoon'10. (Joint with B. Ma and L. Wang.)
4. Fast Exact Algorithms for the Closest String and Substring Problems with Application to the Planted (L,d)-Motif Model. IEEE/ACM Transactions on Computational Biology and Bioinformatics.
5. An Approximation Algorithm for the Minimum Co-Path Set Problem. Algorithmica.
6. HybridNet: A Tool for Constructing Hybridization Networks. Bioinformatics.
7. Approximating Maximum Edge 2-Coloring in Simple Graphs. Discrete Applied Mathematics. Presented at AAIM'10.
8. A Deterministic Approximation Algorithm for Maximum 2-Path Packing. IEICE Transactions.
9. Improved Approximation Algorithms for Reconstructing the History of Tandem Repeats. IEEE/ACM Transaction on Computational Biology and Bioinformatics.
10. Approximating maximum edge 2-coloring in simple graphs via local improvement. AAIM'08. Full version was invited to a special issue of Theoretical Computer Science on AAIM'08.
11. An improved randomized approximation algorithm for maximum triangle packing. AAIM'08. Full version appeared in Discrete Applied Mathematics.
12. Approximation algorithms for reconstructing the duplication history of tandem repeats. (COCOON'2007). Also invited to Algorithmica. (Joint with L. Wang and Z. Wang.)
13. An improved approximation algorithm for maximum edge 2-coloring in simple graphs. AAIM'07. Full version appeared in Journal of Discrete Algorithms.
14. Approximation algorithms for bounded degree phylogenetic roots. Algorithmica.
15. Heuristic search in constrained bipartite matching with applications to protein NMR backbone resonance assignment. Journal of Bioinformatics and Computational Biology. (Joint with G. Lin and T. Tegos.)
16. Recognizing hole-free 4-map graphs in cubic time. Algorithmica.
17. Improved approximation algorithms for metric Max TSP. ESA'2005. Full version appeared in Journal of Combinatorial Optimization.
18. An improved randomized approximation algorithm for Max TSP. Journal of Combinatorial Optimization.
19. Improved deterministic approximation algorithms for Max TSP. Information Processing Letters.
20. New bounds on the number of edges in a k-map graph. CoCoon'2004. Full version appeared in Journal of Graph Theory.
21. Computing phylogenetic roots with bounded degrees and errors is hard. CoCoon'2004. (Joint with T. Tsukiji.) Full version was invited to a special issue (on the CoCoon2004 conference) of Theoretical Computer Science.
22. Protein NMR peak assignment: algorithms and complexity. SCI'2004.
23. Computing bounded-degree phylogenetic roots of disconnected graphs. WG'2004. Full version appeared in Journal of Algorithms.
24. More reliable protein NMR peak assignment via improved 2-interval scheduling. ESA'2003. (Joint with J. Wen, ...) Full version appeared in Journal of Computational Biology.
25. A linear-time algorithm for 7-coloring 1-planar graphs. MFCS'2003. Full version appeared in Algorithmica.
26. A space efficient algorithm for sequence alignment with inversions. CoCoon'2003. (Joint with G.-H. Lin, ...) Full version was invited to a special issue (on the CoCoon2003 conference) of Theoretical Computer Science.
27. An efficient branch-and-bound algorithm for the assignment of protein backbone NMR peaks . CSB2002 (the IEEE Computer Society Bioinformatics Conference). (Joint with G.-H. Lin, D. Xu, ...) Full version was invited to a special issue (on the CSB2002 conference) of Journal of Bioinformatics and Computational Biology.
28. Approximation algorithms for NMR spectral peak assignment . Theoretical Computer Science. (Joint with T. Jiang, G.-H. Lin, ...) A new version with better results was presented at WABI2002.
29. Map graphs. Journal of the ACM. (Joint with M. Grigni and C.H. Papadimitriou.)
30. Computing phylogenetic roots with bounded degrees and errors. . WADS'2001. (Joint with T. Jiang and G.-H. Lin.) Full version appeared in SIAM Journal on Computing.
31. The longest common subsequence problem for sequences with nested arc annotations. . ICALP'2001. (Joint with G.-H. Lin, T. Jiang and J. Wen.) Full version appeared in a special issue of Journal of Computer and System Sciences.
32. Parallel approximation algorithms for maximum weighted matching in general graphs. IFIP TCS2000. (Joint with R. Uehara.) Part of the results appeared in Information Processing Letters.
33. Approximation algorithms for independent sets in map graphs. CoCoon'2000. Full version appeared in Journal of Algorithms.
34. Hierarchical topological inference on planar disc maps. CoCoon'2000. (Joint with X. He.) The revised version appeared in Algorithmica.
35. Finding double Euler trails of planar graphs in linear time. FOCS'99. (Joint with X. He.) Full version appeared in SIAM Journal on Computing.
36. Common-face embeddings of planar graphs. A preliminary version was presented at SODA'99. (Joint with X. He and M.-Y. Kao.) Full version appeared in SIAM Journal on Computing.