Leizhen Cai

Publication Activity (10 Years)

Years Active: 1991-2019
Publications (10 Years): 5

Top Topics

Parameterized Complexity

Minimum Spanning Trees

Edge Information

Top Venues

Theor. Comput. Sci.

Publications

Ho Lam Pang, Leizhen Cai
Complexity of Vertex Switching on Edge-Bicolored Graphs. CIAC (2019)
Leizhen Cai, Junjie Ye
Two edge-disjoint paths with length constraints. Theor. Comput. Sci. 795 (2019)
Leizhen Cai
Vertex Covers Revisited: Indirect Certificates and FPT Algorithms. CoRR (2018)
Leizhen Cai, On Yin Leung
Alternating Path and Coloured Clustering. CoRR (2018)
Leizhen Cai, Junjie Ye
Finding Two Edge-Disjoint Paths with Length Constraints. WG (2016)
Leizhen Cai, Yufei Cai
Incompressibility of H-Free Edge Modification Problems. Algorithmica 71 (3) (2015)
Leizhen Cai, Siu-Wing Cheng, Tak Wah Lam
Guest Editors Foreword. Algorithmica 73 (4) (2015)
Leizhen Cai, Junjie Ye
Parameterized complexity of finding connected induced subgraphs. Theor. Comput. Sci. 607 (2015)
Chengwei Guo, Leizhen Cai
Obtaining split graphs by edge contraction. Theor. Comput. Sci. 607 (2015)
Leizhen Cai, Junjie Ye
Finding Two Edge-Disjoint Paths with Length Constraints. CoRR (2015)
Leizhen Cai, Junjie Ye
Parameterized Complexity of Connected Induced Subgraph Problems. AAIM (2014)
Leizhen Cai, Junjie Ye
Dual Connectedness of Edge-Bicolored Graphs and Beyond. MFCS (2) (2014)
Chengwei Guo, Leizhen Cai
Obtaining Split Graphs by Edge Contraction. AAIM (2014)
Leizhen Cai, Chengwei Guo
Contracting Graphs to Split Graphs and Threshold Graphs. CoRR (2013)
Leizhen Cai, Yufei Cai
Incompressibility of H-Free Edge Modification. IPEC (2013)
Leizhen Cai, Chengwei Guo
Contracting Few Edges to Remove Forbidden Induced Subgraphs. IPEC (2013)
Mingyu Xiao, Leizhen Cai, Andrew Chi-Chih Yao
-Way Cut Problem. Algorithmica 59 (4) (2011)
Leizhen Cai, Boting Yang
Parameterized complexity of even/odd subgraph problems. J. Discrete Algorithms 9 (3) (2011)
Leizhen Cai, Weifan Wang, Xuding Zhu
Choosability of toroidal graphs without short cycles. J. Graph Theory 65 (1) (2010)
Leizhen Cai, Yongxi Cheng, Elad Verbin, Yuan Zhou
Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem. SIAM J. Discret. Math. 24 (4) (2010)
Leizhen Cai, Boting Yang
Parameterized Complexity of Even/Odd Subgraph Problems. CIAC (2010)
Leizhen Cai, Weifan Wang
The Surviving Rate of a Graph for the Firefighter Problem. SIAM J. Discret. Math. 23 (4) (2009)
Weifan Wang, Leizhen Cai
Labelling planar graphs without 4-cycles with a condition on distance two. Discret. Appl. Math. 156 (12) (2008)
Leizhen Cai
Parameterized Complexity of Cardinality Constrained Optimization Problems. Comput. J. 51 (1) (2008)
Leizhen Cai, Elad Verbin, Lin Yang
Firefighting on Trees: (1-1/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm. ISAAC (2008)
Mingyu Xiao, Leizhen Cai, Andrew C. Yao
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem CoRR (2008)
Leizhen Cai, Siu Man Chan, Siu On Chan
Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems. IWPEC (2006)
Leizhen Cai
The complexity of the locally connected spanning tree problem. Discret. Appl. Math. 131 (1) (2003)
Leizhen Cai
Parameterized Complexity of Vertex Colouring. Discret. Appl. Math. 127 (3) (2003)
Leizhen Cai, Derek G. Corneil, Andrzej Proskurowski
)-intersection graphs. Discret. Math. 230 (1-3) (2001)
Leizhen Cai, Xuding Zhu
-degenerate graphs. J. Graph Theory 36 (3) (2001)
Leizhen Cai, Yin-Feng Xu, Binhai Zhu
Computing the Optimal Bridge Between Two Convex Polygons. Inf. Process. Lett. 69 (3) (1999)
Leizhen Cai
On Spanning 2-trees in a Graph. Discret. Appl. Math. 74 (3) (1997)
Leizhen Cai, J. Mark Keil
Computing Visibility Information in an Inaccurate Simple Polygon. Int. J. Comput. Geom. Appl. 7 (6) (1997)
Leizhen Cai, Baruch Schieber
A Linear-time Algorithm for Computing the Intersection of All Odd Cycles in a Graph. Discret. Appl. Math. 73 (1) (1997)
Leizhen Cai, Derek G. Corneil
-perfect graphs. J. Graph Theory 23 (1) (1996)
Leizhen Cai
Algorithms on Polygonal Embeddings of Graphs. CCCG (1996)
Leizhen Cai
Fixed-Parameter Tractability of Graph Modification Problems for Hereditary Properties. Inf. Process. Lett. 58 (4) (1996)
Leizhen Cai, Derek G. Corneil, Andrzej Proskurowski
)-intersection graphs. J. Graph Theory 21 (3) (1996)
Leizhen Cai, Derek G. Corneil
Tree Spanners. SIAM J. Discret. Math. 8 (3) (1995)
Leizhen Cai, Derek G. Corneil
Isomorphic Tree Spanner Problems. Algorithmica 14 (2) (1995)
Leizhen Cai
Spanning 2-Trees. ASIAN (1995)
Leizhen Cai
Path decompositions of multigraphs. J. Graph Theory 19 (3) (1995)
Leizhen Cai, Hazel Everett
Visibility graphs of polygonal rings. CCCG (1995)
Leizhen Cai, J. Mark Keil
Spanners in graphs of bounded degree. Networks 24 (4) (1994)
Leizhen Cai
NP-Completeness of Minimum Spanner Problems. Discret. Appl. Math. 48 (2) (1994)
Leizhen Cai, J. Mark Keil
Degree-Bounded Spanners. Parallel Process. Lett. 3 (1993)
Leizhen Cai
The Recognition of Union Trees. Inf. Process. Lett. 45 (6) (1993)
Leizhen Cai, Frédéric Maffray
-Tree Problem. Discret. Appl. Math. 44 (1-3) (1993)
Leizhen Cai, Derek G. Corneil
On cycle double covers of line graphs. Discret. Math. 102 (1) (1992)
Leizhen Cai, John A. Ellis
Edge colouring line graphs of unicyclic graphs. Discret. Appl. Math. 36 (1) (1992)
Leizhen Cai, John A. Ellis
NP-completeness of edge-colouring some restricted graphs. Discret. Appl. Math. 30 (1) (1991)