CAI, Leizhen (Professor)

Ph.D., University of Toronto, 1992
M.Sc., University of Victoria, 1988
B.Sc., Zhejiang University, 1982
Department of Computer Science and Engineering
The Chinese University of Hong Kong
Shatin, Hong Kong SAR, CHINA

Phone: (852)39438425 Fax: (852)26035024 Email: with username lcai

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

CSC3160 Design and Analysis of Algorithms
CSC5320 Topics in Graph Algorithms
ENGG1410E Engineering Mathematics I

Hobby: Stone carving

Representative Publications

  1. L. Cai and Y. Cai, Incompressibility of H-Free Edge Modification Problems, to appear in Algorithmica : spcial issus for IPEC 2013 (extended abstract in LNCS 8246, pp. 84-96, 2013).

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

  3. L. Cai and C. Guo, Contracting Few Edges to Remove Forbidden Induced Subgraphs, IPEC 2013, LNCS 8246, pp. 97-109, 2013.

  4. L. Cai and B. Yang, Parameterized Complexity of Even/Odd Subgraph Problems , Journal of Discrete Algorithms , Vol 9(3) 231-240, 2011.

  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, H.L. Bodlaender and M.A. Langston(Eds.): 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.