CAI, Leizhen (Professor) Ph.D., University of Toronto, 1992 M.Sc., University of Victoria, 1988 B.Sc., Zhejiang University, 1982

Phone: (852)26098425 Fax: (852)26035024 Email: (username lcai) cse.cuhk.edu.hk

CSC5320 Topics in Graph Algorithms
CSC3160 Design and Analysis of Algorithms

Representative Publications

1. L. Cai and B. Yang, Parameterized complexity of even/odd subgraph problems , Journal of Discrete Algorithms , Vol 9(3) 231-240, 2011.

2. 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.

3. L. Cai, Y. Cheng, E. Verbin, and Y. Zhou, Surviving rates of graphs with bounded treewidth for the firefighter problem , SIAM Journal on Discrete Mathematics , Vol 24(4) 1322-1335, 2010.

4. 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.

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

6. 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.

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

8. L. Cai and X. Zhu, Game Chromatic Index of k-Degenerate Graphs, Journal of Graph Theory, 36(3) 144-155, 2001.

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

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

11. L. Cai, Path Decompositions of Multigraphs, Journal of Graph Theory, 19(3), 297-307, 1995.