Um algoritmo de planos de corte para o problema livre de garra: estudo poliédrico e implementação Branch-and-Cut

Abstract

Let G = (V;E) be a simple graph, where V is the set of vertices and E is the set of edges. A claw is de ned as a complete bipartite graph K1,3. The Claw-free problem (CFP) aims at nding a minimum subset of vertices S c V such that none of the vertex-induced subgraphs of G[V n S] are claws. The present work performs a polyhedral study on the CFP, which is a NP-complete problem, presenting 2 integer programming models(Fg and FSk ), where FSk is implemented with a cutting plane-based procedure. Computational experiments were performed in instances with di erent densities with up to 100 vertices. The results obtained suggest that FSk had a superior performance when compared to Fg.