A comparison of integer and constraint programming models for the deficiency problem. (April 2016)

• Record Type: Journal Article
• Authors: Altinakar, Sivan; Caporossi, Gilles; Hertz, Alain
• Is Part Of: Computers & operations research. Volume 68(2016)
• Page Start: 89
• Page End: 96
• Publication Date: 2016-04
• Subjects: Compact edge-colorings -- Integer linear programming -- Constraint programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.10.016
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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, … } to every edge e ∈ E so that adjacent edges are assigned different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form a set 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. Abstract : Highlights: We describe integer and constraint programming models for the deficiency problem. We obtain bounds on the number of colors in an edge-coloring with minimum deficiency. We clearly show that symmetry breaking constraints decrease the computing time.