CAI Leizhen, CUHK CSE

Professor CAI Leizhen

Ph.D., University of Toronto, 1992 (supervisor: Derek Corneil)
M.Sc., University of Victoria, 1988 (supervisor: John Ellis)
B.Sc., Zhejiang University, 1982
Photo
Department of Computer Science and Engineering
The Chinese University of Hong Kong
Shatin, Hong Kong SAR, CHINA

Phone: (852)39438425 Fax: (852)26035024 Email: lcai@cse.cuhk.edu.hk


Research Interests: FPT algorithms, graph algorithms, and graph theory.

Teaching:
CSCI5320 Topics in Graph Algorithms Color Coding   Random Separation
CSCI3160 Design and Analysis of Algorithms   Finale (Video by MA Siu Tong)

Other courses:
ENGG1410 Engineering Mathematics
CSCI2100 Discrete Mathematics
CSCI2110 Data Structures
ENGG2440 Discrete Mathematics for Engineers
ESTR3104 Design and Analysis of Algorithms (Elite Class)
CSC3640 Introduction to Theoretical Computer Science
CSC6160 Algorithmic Graph Theory
CSC7120 Computational Complexity

Hobby: Stone carving


Representative Publications

  1. L. Cai and J. Ye, Two Edge-Disjoint Paths with Length Constraints, Theoretical Computer Science, Vol 795 275-284, 2019.

  2. L. Cai, Vertex Covers Revisited: Indirect Certificates and FPT Algorithms, arXiv:1807.11339, 2018.

  3. L. Cai and Y. Cai, Incompressibility of H-Free Edge Modification Problems, Invited paper for IPEC 2013, Algorithmica 71(3) 731-757, 2015.

  4. L. Cai and J. Ye, Dual Connectedness of Edge-Bicolored Graphs and Beyond, MFCS 2014, LNCS 8635, pp. 141-152, 2014.

  5. M. Xiao, L. Cai, and A.C.C. Yao, Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem, Algorithmica Vol 59 510-520, 2011.

  6. L. Cai and W. Wang, The Surviving Rate of a Graph for the Firefighter Problem, SIAM Journal on Discrete Mathematics , 23(4) 1814-1826, 2009.

  7. L. Cai, Parameterized Complexity of Cardinality Constrained Optimization Problems, the Computer Journal 51(1) 102-121, 2008.

  8. L. Cai, E. Verbin and L. Yang, Firefighting on Trees: (1 - 1/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm , ISAAC 2008, LNCS 5369, pp. 258-269, 2008.

  9. L. Cai, S.M. Chan and S.O. Chan, Random Separation: a New Method for Solving Fixed-Cardinality Optimization Problems, IWPEC 2006, LNCS 4169, pp. 239-250, 2006.

  10. L. Cai, Parameterized Complexity of Vertex Colouring, Discrete Applied Mathematics, 127(3) 415-429, 2003.

  11. L. Cai, Fixed-parameter tractability of graph modification problems for hereditary properties, Information Processing Letters, 58, 171-176, 1996.

  12. L. Cai and D.G. Corneil, Tree Spanners, SIAM Journal on Discrete Mathematics, 8(3), 359-387, 1995.