4 citations · 5 across the 5 of their papers we have counts for
5 papers
Vertex Covers Revisited: Indirect Certificates and FPT Algorithms
Leizhen Cai
The classical NP-complete problem Vertex Cover requires us to determine whether a graph contains at most vertices that cover all edges. In spite of its intractability, the prob…
Alternating Path and Coloured Clustering
Leizhen CAI, On Yin LEUNG
In the Coloured Clustering problem, we wish to colour vertices of an edge coloured graph to produce as many stable edges as possible, i.e., edges with the same colour as their ends…
Finding Two Edge-Disjoint Paths with Length Constraints
Leizhen Cai, Junjie Ye
We consider the problem of finding, for two pairs and of vertices in an undirected graphs, an -path and an -path such that…
Contracting Graphs to Split Graphs and Threshold Graphs
Leizhen Cai, Chengwei Guo
We study the parameterized complexity of Split Contraction and Threshold Contraction. In these problems we are given a graph G and an integer k and asked whether G can be modified…
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem
Mingyu Xiao, Leizhen Cai, Andrew C. Yao
For an edge-weighted connected undirected graph, the minimum -way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into con…