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: @cse.cuhk.edu.hk with username lcai



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


Teaching:
CSC5320 Topics in Graph Algorithms
CSC3160 Design and Analysis of Algorithms


Hobby: Stone carving



Representative Publications

  1. L. Cai and Y. Cai, Incompressibility of H-Free Edge Modification Problems, to appear in Algorithmica : invited paper 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.

  • DH