18 citations · 29 across the 10 of their papers we have counts for
16 papers · 1 filter
Cluster Deletion is as Hard to Approximate as Vertex Cover
Yixin Cao, Ying Xu
Recent breakthroughs in Cluster Editing have motivated attempts to adapt these approaches to obtain better-than- approximations for Cluster Deletion. We rule out this possibilit…
Cluster Vertex Deletion on Chordal Graphs
Yixin Cao, Peng Li
We present a polynomial-time algorithm for the cluster vertex deletion problem on chordal graphs, resolving an open question posed in different contexts by Cao et al. [Theoretical…
Modification Problems toward Proper (Helly) Circular-arc Graphs
Yixin Cao, Jianxin Wang, Hanchun Yuan
We present a -time algorithm for the proper circular-arc vertex deletion problem, resolving an open problem of van 't Hof and Villanger [Algorithmica 2013] and C…
(Sub)linear kernels for edge modification problems towards structured graph classes
Gabriel Bathie, Nicolas Bousquet, Théo Pierron
In a (parameterized) graph edge modification problem, we are given a graph , an integer and a (usually well-structured) class of graphs , and ask whether it is…
Improved Kernels for Edge Modification Problems
Yixin Cao, Yuping Ke
In an edge modification problem, we are asked to modify at most edges to a given graph to make the graph satisfy a certain property. Depending on the operations allowed, we hav…
Recognizing (Unit) Interval Graphs by Zigzag Graph Searches
Yixin Cao
Corneil, Olariu, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete…