Paula Zabala

A cutting plane algorithm for graph coloring

2008, Discrete Applied Mathematics 156 (2), 159-179, 2008
Citas: 130
Agregar PDF Importar citas Importar citas SCRAPME Plots Conexiones

Autor(es)

Isabel Méndez-Díaz and Paula Zabala

URL Pública

https://www.sciencedirect.com/science/article/pii/S0166218X0700100X

Abstract

We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm.

Plot de citas