4 papers
Exploring subgraph complementation to bounded degree graphs
Ivo Koch, Nina Pardal, Vinicius F. dos Santos
Graph modification problems are computational tasks where the goal is to change an input graph using operations from a fixed set, in order to make the resulting graph satisfy a…
Edge deletion to tree-like graph classes
Ivo Koch, Nina Pardal, Vinicius Fernandes dos Santos
For a fixed property (graph class) , given a graph G and an integer k, the -deletion problem consists in deciding if we can turn into a graph with the property by del…
On the proper interval completion problem within some chordal subclasses
François Dross, Claire Hilaire, Ivo Koch +4
Given a property (graph class) , a graph , and an integer , the \emph{-completion} problem consists in deciding whether we can turn into a graph with the property $…
General Cut-Generating Procedures for the Stable Set Polytope
Ricardo C. Corrêa, Diego Delle Donne, Ivo Koch +1
We propose general separation procedures for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and…