The convex recoloring problem: polyhedra, facets and computational experiments (Q263202): Difference between revisions
From MaRDI portal
Latest revision as of 17:56, 11 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The convex recoloring problem: polyhedra, facets and computational experiments |
scientific article |
Statements
The convex recoloring problem: polyhedra, facets and computational experiments (English)
0 references
4 April 2016
0 references
This article considers the convex recoloring problem on graphs. Given a graph, a convex coloring of vertices is defined as one where the set of vertices having the same color is connected. The authors study the problem of converting any graph coloring into a convex coloring by modifying the color of the minimum number of vertices. The paper begins with an introduction to graph coloring and the background definitions in this area, followed by a novel integer programming formulation of the convex recoloring problem. Then the authors proceed to study the convex polytope defined by the feasible integer solutions of the integer program and derive, with proof, by facet-defining inequalities for this polyhedron. The third section concentrates on the facets that correspond to trees where further facet-defining inequalities are produced. In order to use these inequalities in a branch-and-cut framework, a polynomial-time separation algorithm to generate these inequalities from any fractional relaxation solution is described. The last section of this very interesting article contains the results of extensive computational experimentation evaluating the proposed algorithm.
0 references
convex coloring
0 references
facet
0 references
integer linear programming
0 references
polyhedral study
0 references
branch-and-cut
0 references
phylogenetic tree
0 references