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
Also taught Computability and Complexity (CSC364) at University of
Toronto,
a graduate course Parameterized Complexity at Tsinghua University, and
an undergraduate course Programming in Pascal at Zhejiang University.
Hobby: Stone carving
Representative Publications
- L. Cai,
Vertex Covers Revisited: Indirect Certificates and FPT Algorithms, revision of
arXiv:1807.11339, 2025.
- L. Cai and J. Ye,
Two Edge-Disjoint Paths with Length Constraints,
Theoretical Computer Science, Vol 795 275-284, 2019.
- L. Cai and Y. Cai,
Incompressibility of H-Free Edge Modification Problems,
Invited paper for IPEC 2013, Algorithmica 71(3) 731-757, 2015.
- L. Cai and J. Ye,
Dual Connectedness of Edge-Bicolored Graphs and Beyond,
MFCS 2014, LNCS 8635, pp. 141-152, 2014.
- 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.
- 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.
- L. Cai,
Parameterized Complexity of Cardinality Constrained Optimization Problems,
the Computer Journal 51(1) 102-121, 2008.
- 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.
- 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.
- L. Cai,
Parameterized Complexity of Vertex Colouring,
Discrete Applied Mathematics, 127(3) 415-429, 2003.
- L. Cai,
Fixed-parameter tractability of graph modification problems
for hereditary properties,
Information Processing Letters, 58, 171-176, 1996.
- L. Cai and D.G. Corneil,
Tree Spanners,
SIAM Journal on Discrete Mathematics, 8(3), 359-387, 1995.
