Group for Research in Decision Analysis

G-2014-25

A comparison of integer and constraint programming models for the deficiency problem

, , and

An edge-coloring of a graph \(G=(V,E)\) is a function \(c\) that assigns an integer \(c(e)\) (called color) in \(\{0,1,2,\dotsc\}\) to every edge \(e\in E\) so that adjacent edges share different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form an interval of consecutive integers. The deficiency problem is to determine the minimum number of pendant edges that must be added to a graph such that the resulting graph admits a compact edge-coloring. We propose and analyze three integer programming models and one constraint programming model for the deficiency problem.

, 16 pages