8 citations · 10 across the 3 of their papers we have counts for
5 papers · 1 filter
(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…
Polynomial Kernels for Paw-free Edge Modification Problems
Yixin Cao, Yuping Ke, Hanchun Yuan
Let be a fixed graph. Given a graph and an integer , the -free edge modification problem asks whether it is possible to modify at most edges in to make it …
Vertex Deletion Problems on Chordal Graphs
Yixin Cao, Yuping Ke, Yota Otachi +1
Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis an…
Unit Interval Vertex Deletion: Fewer Vertices are Relevant
Yuping Ke, Yixin Cao, Xiating Ouyang +1
The unit interval vertex deletion problem asks for a set of at most vertices whose deletion from an -vertex graph makes it a unit interval graph. We develop an -vert…