31 citations · 126 across the 26 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021
(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…
math.CO2021
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…
cs.DS2021
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…