4 papers
A column generation algorithm for finding co-3-plexes in chordal graphs
Alexandre Dupont-Bouillard
In this study, we tackle the problem of finding a maximum \emph{co-3-plex}, which is a subset of vertices of an input graph, inducing a subgraph of maximum degree 2. We focus on th…
Extended formulations for the maximum weighted co-2-plex problem
Alexandre Dupont-Bouillard, Pierre Fouilhoux, Roland Grappe +1
Given an input graph and weights on its vertices, the maximum co-2-plex problem is to find a subset of vertices maximizing the sum of their weights and inducing a graph of degree a…
Extended formulations for induced tree and path polytopes of chordal graphs
Alexandre Dupont-Bouillard
In this article, we give two extended space formulations, respectively, for the induced tree and path polytopes of chordal graphs with vertex and edge variables. These formulations…
Contractions in perfect graph
Alexandre Dupont-Bouillard, Pierre Fouilhoux, Roland Grappe +1
In this paper, we characterize the class of {\em contraction perfect} graphs which are the graphs that remain perfect after the contraction of any edge set. We prove that a graph i…