Research Interests

Parameterized Complexity and Algorithms, Combinatorial Optimization, Graph Algorithms, Computational Geometry, Computational Biology, Mobile Computing and Distributed Algorithms. 

Publications

Note. All co-authors appear in alphabetical order. Papers are available upon request.

Journal Publications

• On the Pseudo-Achromatic Problem. Theoretical Computer Science 410 (8-10), pages 818-829, 2009. Earlier version appeared in proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG),  Lecture Notes in Computer Science 5344, pages 78-89, 2008. (With J. Chen, J. Meng, G. Xia, and F. Zhang)
   
• Strictly Localized Construction of Near-Optimal Power Spanners for Wireless Ad-Hoc Networks. To appear in the IEEE Transactions on Mobile Computing. Earlier version appeared in proceedings of the 4th ACM SIGACT-SIGOPS International Workshop on Foundations of Mobile Computing (DIAL-M-POMC), 2007. (With L. Perkovic and G. Xia)
   
• On the Induced Matching Problem. To appear in the Journal of Computer and System Sciences. Earlier version appeared in proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 397-408, 2008. (With M. Pelsmajer, M. Schaefer, and G. Xia)
   
• Seeing the trees and their branches in the network is hard. Theoretical Computer Science (1-3), pages 153-164, 2008. Earlier version appeared in the proceedings of the 10th Italian Conference on Theoretical Computer Science (ICTCS), pages 82-93, 2007. (With L. Nakhleh, C. Thuan, and G. Xia)
   
• The Compatibility of Binary Characters on Phylogenetic Networks: Complexity and Parameterized Algorithms. Algorithmica 51-2, pages 99-128, 2008.  Earlier version appeared in proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science 4112, pages 299-308, 2006.
   
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size. SIAM Journal on Computing 37-4, pages 1077-1106, 2007. Earlier version appeared  in proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), 
  Lecture Notes in Computer Science 3404, pages 269-280, (2005). (With J. Chen, H. Fernau, and G. Xia)
   
• Genus Characterizes the Complexity of NP-hard Graph Problems: Some Tight Results.
  Journal of Computer and System Sciences 73-6, pages 892-907, 2007. Earlier version appeared in Proceedings of the 30th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science 2719, pages 845 -856,  2003. (With J. Chen, L. Perkovic', E. Sedgwick, and G. Xia)
   
•  Polynomial Time Approximation Schemes and Parameterized Complexity. Discrete Applied Mathematics 155-2, pages 180-193, 2007. Earlier version appeared in the proceedings of the 29th International Symposium on the Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science 3153, pages 500-512, 2004.  (With  J. Chen, X. Huang, and G. Xia)
   
•  Linear FPT reductions and computational lower bounds. Journal of Computer and System Sciences 72-8,  pages 1346-1367, 2006.
   Earlier version appeared in the proceedings of the 36th ACM Symposium on Theory of Computing (STOC),  pages 212-221, 2004.   (With  J. Chen, X. Huang, and G. Xia)
   
• The W-Hardness under Linear FPT-Reductions: Structural Properties and Further Applications. Journal of Combinatorial Optimization 11, 2006, pages 231-247. Earlier version appeared in the proceedings of the Eleventh International Computing and Combinatorics Conference (COCOON), Lecture Notes in Computer Science 3595, pages 975-984, 2005. (With  J. Chen, X. Huang, and G. Xia)
   
• Tight lower bounds for parameterized NP-hard problems. Information & Computation 201,  pages 216-231, 2005.
  Earlier version appeared in the proceedings of the 19th IEEE Conference on Computational Complexity (CCC),
  pages 150-160, 2004. (With J. Chen, B. Chor, M. Fellows, X. Huang, D. Juedes, and G. Xia)
  
  
• Hypercube Network Fault Tolerance: A Probabilistic Approach. Journal of Interconnection Networks 6-1, pages 17-34, 2005 . Earlier version appeared in proceedings of the 31st International Conference on Parallel Processing. pages 65-72, 2002.
  (With J. Chen and G. Wang)
  
  
• On Approximating Minimum Vertex Cover for Graphs with Perfect Matching. Theoretical Computer Science 337, pages 305-318, 2005. Earlier version appeared in proceedings of the 11th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 1969, pages 132-143, 2000.  (With J. Chen)
   
• Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for NP-hard Problems. Algorithmica 43,  pages 245-273, (2005).  Earlier version appeared in the proceedings of the 14th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 2906, pp. 148--157, 2003.  (With J. Chen and G. Xia)
   
•  Using Nondeterminism to Design Efficient Deterministic Algorithms,  Algorithmica 40, pages 83-97, 2004.
   Earlier version appeared in proceedings of  the 21st International Conference on Foundations of Software Technology
   and Theoretical Computer Science (FSTTCS), Lecture Notes in Computer Science 2245, pages 120-131, 2001.
   (With J. Chen, D. K. Friesen, and W. Jia) 
   
• Improved Exact Algorithms for Max-Sat,  Discrete Applied Mathematics 142, pages 17-27, 2004.  Earlier version appeared in proceedings of the 5th Latin American Symposium on Theoretical Informatics (LATIN),  Lecture Notes in Computer Science 2286, pages 341-355, 2002. (With J. Chen)
   
• Constrained Minimum Vertex Cover in Bipartite Graph: Complexity and Parameterized Algorithms.  Journal of Computer and System Sciences 67-4, pages 833-847, 2003. (With J. Chen)
   
• Inapproximability of non NP-hard optimization problems. Theoretical Computer Science 289, pp. 553-571, 2002). Earlier version appeared in proceedings of the 9th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 1533, pages 437-446, 1998. (With L. Cai and D. Juedes) 
  
  
• Vertex Cover, Further Observations and Further Improvements. Journal of Algorithms  41, pp. 280-301, 2001. Earlier version appeared in the proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science 1665, pages 313-324, 1999.  Also presented at the Workshop on Faster Exact Algorithms for NP-hard Problems
  organized by DIMACS, Princeton, February 23-24, 2000.  (With J. Chen and W. Jia)

Conference Publications (not listed above)

• Computing Lightweight Spanners Locally. In proceedings of the 22nd International Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science 5218, pages 365-378, 2008. (With L. Perkovic and G. Xia)
   
• On Geometric Spanners of Euclidean and Unit Disk Graphs. In proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 409-420, 2008. (With L. Perkovic)
   
• Separability and Topology Control of Quasi Unit Disk Graphs. In proceedings of the 26th Annual IEEE Conference on
  Computer Communication  (INFOCOM), pages 2225-2233, 2007. (With J. Chen,  A. Jiang, G. Xia, and F. Zhang)
   
• Improved Stretch Factor for Bounded-Degree Planar Power Spanners of Wireless Ad-Hoc Networks. In proceedings of the 2nd International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSOR),  Lecture Notes in Computer Science 4240, pages 95-106, 2006. (With L. Perkovic)
   
• On the Effective Enumerability of NP problems. In proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC),  Lecture Notes in Computer Science 4169, pages 215-226, 2006. (With J. Chen, J. Meng, G. Xia, and F. Zhang)
   
•  Improved Upper Bounds for Vertex Cover. In proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science 4162, pages 238-249, 2006.  (With J. Chen and G. Xia)
   
• Parameterized Algorithms for Feedback Vertex Set, in proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC), Lecture Notes in Computer Science 3162, pp. 235-247, 2004. (With M. Pelsmajer and M. Schaefer)
   
•   Improved Parameterized Algorithms for Planar Dominating Set, in proceedings of the 27th Annual Symposium on the Foundations of  Computer  Science  (MFCS), Lecture Notes in Computer Science 2420, pp. 399-410, 2002.  (With Ljubomir Perkovic)
   
• Minimum fault coverage in reconfigurable arrays: complexity and improved algorithms,  in proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Lecture Notes in Computer Science 2204, pp. 55-65, 2001.  (With J. Chen)