Leizhen Cai

According to our database, Leizhen Cai authored at least 50 papers between 1991 and 2019.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2019

Two edge-disjoint paths with length constraints.

Leizhen Cai, Junjie Ye

Theor. Comput. Sci., 2019

Complexity of Vertex Switching on Edge-Bicolored Graphs.

Ho Lam Pang, Leizhen Cai

Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2018

Vertex Covers Revisited: Indirect Certificates and FPT Algorithms.

Leizhen Cai

CoRR, 2018

Alternating Path and Coloured Clustering.

Leizhen Cai, On Yin Leung

CoRR, 2018

2016

Finding Two Edge-Disjoint Paths with Length Constraints.

Leizhen Cai, Junjie Ye

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2016

2015

Obtaining split graphs by edge contraction.

Chengwei Guo, Leizhen Cai

Theor. Comput. Sci., 2015

Parameterized complexity of finding connected induced subgraphs.

Leizhen Cai, Junjie Ye

Theor. Comput. Sci., 2015

Guest Editors Foreword.

Leizhen Cai, Siu-Wing Cheng, Tak Wah Lam

Algorithmica, 2015

Incompressibility of H-Free Edge Modification Problems.

Leizhen Cai, Yufei Cai

Algorithmica, 2015

2014

Dual Connectedness of Edge-Bicolored Graphs and Beyond.

Leizhen Cai, Junjie Ye

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Parameterized Complexity of Connected Induced Subgraph Problems.

Leizhen Cai, Junjie Ye

Proceedings of the Algorithmic Aspects in Information and Management, 2014

2013

Contracting Graphs to Split Graphs and Threshold Graphs.

Leizhen Cai, Chengwei Guo

CoRR, 2013

Contracting Few Edges to Remove Forbidden Induced Subgraphs.

Leizhen Cai, Chengwei Guo

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

Incompressibility of H-Free Edge Modification.

Leizhen Cai, Yufei Cai

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

2011

Parameterized complexity of even/odd subgraph problems.

Leizhen Cai, Boting Yang

J. Discrete Algorithms, 2011

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum <i>k</i>-Way Cut Problem.

Mingyu Xiao, Leizhen Cai, Andrew Chi-Chih Yao

Algorithmica, 2011

2010

Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem.

Leizhen Cai, Yongxi Cheng, Elad Verbin, Yuan Zhou

SIAM J. Discret. Math., 2010

Choosability of toroidal graphs without short cycles.

Leizhen Cai, Weifan Wang, Xuding Zhu

J. Graph Theory, 2010

2009

The Surviving Rate of a Graph for the Firefighter Problem.

Leizhen Cai, Weifan Wang

SIAM J. Discret. Math., 2009

2008

Labelling planar graphs without 4-cycles with a condition on distance two.

Weifan Wang, Leizhen Cai

Discret. Appl. Math., 2008

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

Mingyu Xiao, Leizhen Cai, Andrew C. Yao

CoRR, 2008

Parameterized Complexity of Cardinality Constrained Optimization Problems.

Leizhen Cai

Comput. J., 2008

Firefighting on Trees: (1-1/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm.

Leizhen Cai, Elad Verbin, Lin Yang

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2006

Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems.

Leizhen Cai, Siu Man Chan, Siu On Chan

Proceedings of the Parameterized and Exact Computation, Second International Workshop, 2006

2003

The complexity of the locally connected spanning tree problem.

Leizhen Cai

Discret. Appl. Math., 2003

Parameterized Complexity of Vertex Colouring.

Leizhen Cai

Discret. Appl. Math., 2003

2001

Game chromatic index of <i>k</i>-degenerate graphs.

Leizhen Cai, Xuding Zhu

J. Graph Theory, 2001

Stable 2-pairs and (<i>X, Y</i>)-intersection graphs.

Leizhen Cai, Derek G. Corneil, Andrzej Proskurowski

Discret. Math., 2001

1999

Computing the Optimal Bridge Between Two Convex Polygons.

Leizhen Cai, Yin-Feng Xu, Binhai Zhu

Inf. Process. Lett., 1999

1997

Computing Visibility Information in an Inaccurate Simple Polygon.

Leizhen Cai, J. Mark Keil

Int. J. Comput. Geom. Appl., 1997

A Linear-time Algorithm for Computing the Intersection of All Odd Cycles in a Graph.

Leizhen Cai, Baruch Schieber

Discret. Appl. Math., 1997

On Spanning 2-trees in a Graph.

Leizhen Cai

Discret. Appl. Math., 1997

1996

A generalization of line graphs: (<i>X, Y</i>)-intersection graphs.

Leizhen Cai, Derek G. Corneil, Andrzej Proskurowski

J. Graph Theory, 1996

A generalization of perfect graphs - <i>i</i>-perfect graphs.

Leizhen Cai, Derek G. Corneil

J. Graph Theory, 1996

Fixed-Parameter Tractability of Graph Modification Problems for Hereditary Properties.

Leizhen Cai

Inf. Process. Lett., 1996

Algorithms on Polygonal Embeddings of Graphs.

Leizhen Cai

Proceedings of the 8th Canadian Conference on Computational Geometry, 1996

1995

Tree Spanners.

Leizhen Cai, Derek G. Corneil

SIAM J. Discret. Math., 1995

Path decompositions of multigraphs.

Leizhen Cai

J. Graph Theory, 1995

Isomorphic Tree Spanner Problems.

Leizhen Cai, Derek G. Corneil

Algorithmica, 1995

Visibility graphs of polygonal rings.

Leizhen Cai, Hazel Everett

Proceedings of the 7th Canadian Conference on Computational Geometry, 1995

Spanning 2-Trees.

Leizhen Cai

Proceedings of the Algorithms, 1995

1994

Spanners in graphs of bounded degree.

Leizhen Cai, J. Mark Keil

Networks, 1994

NP-Completeness of Minimum Spanner Problems.

Leizhen Cai

Discret. Appl. Math., 1994

1993

Degree-Bounded Spanners.

Leizhen Cai, J. Mark Keil

Parallel Process. Lett., 1993

The Recognition of Union Trees.

Leizhen Cai

Inf. Process. Lett., 1993

On the SPANNING <i>k</i>-Tree Problem.

Leizhen Cai, Frédéric Maffray

Discret. Appl. Math., 1993

1992

Tree spanners, spanning trees that approximate distances.

Leizhen Cai

PhD thesis, 1992

On cycle double covers of line graphs.

Leizhen Cai, Derek G. Corneil

Discret. Math., 1992

Edge colouring line graphs of unicyclic graphs.

Leizhen Cai, John A. Ellis

Discret. Appl. Math., 1992

1991

NP-completeness of edge-colouring some restricted graphs.

Leizhen Cai, John A. Ellis

Discret. Appl. Math., 1991