18 citations · 29 across the 7 of their papers we have counts for
17 papers
On Fork-free T-perfect Graphs
Yixin Cao, Shenghua Wang
In an attempt to understanding the complexity of the independent set problem, Chv{á}tal defined t-perfect graphs. While a full characterization of this class is still at large, pro…
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…
Complementation in t-perfect graphs
Yixin Cao, Shenghua Wang
Inspired by applications of perfect graphs in combinatorial optimization, Chvátal defined t-perfect graphs in 1970s. The long efforts of characterizing t-perfect graphs started imm…
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…