Geodesic
Symmetry Breaking Constraints for the Minimum Deficiency Problem
Journal of graph algorithms and applications, Tome 21 (2017) no. 2, pp. 195-218 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

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 receive different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form a set of consecutive integers. The minimum 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. Because of symmetries, an instance of the minimum deficiency problem can have many equivalent optimal solutions. We present a way to generate a set of symmetry breaking constraints, called ${\rm {\small GAMBLLE}}$ constraints, that can be added to a constraint programming model. The ${\rm {\small GAMBLLE}}$ constraints are inspired by the Lex-Leader ones, based on automorphisms of graphs, and act on families of permutable variables. We analyze their impact on the reduction of the number of optimal solutions as well as on the speed-up of the constraint programming model. 
@article{JGAA_2017_21_2_a3,
     author = {Sivan Altinakar and Gilles Caporossi and Alain Hertz},
     title = {Symmetry {Breaking} {Constraints} for the {Minimum} {Deficiency} {Problem}},
     journal = {Journal of graph algorithms and applications},
     pages = {195--218},
     year = {2017},
     volume = {21},
     number = {2},
     doi = {10.7155/jgaa.00412},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00412/}
}
TY  - JOUR
AU  - Sivan Altinakar
AU  - Gilles Caporossi
AU  - Alain Hertz
TI  - Symmetry Breaking Constraints for the Minimum Deficiency Problem
JO  - Journal of graph algorithms and applications
PY  - 2017
SP  - 195
EP  - 218
VL  - 21
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00412/
DO  - 10.7155/jgaa.00412
LA  - en
ID  - JGAA_2017_21_2_a3
ER  - 
%0 Journal Article
%A Sivan Altinakar
%A Gilles Caporossi
%A Alain Hertz
%T Symmetry Breaking Constraints for the Minimum Deficiency Problem
%J Journal of graph algorithms and applications
%D 2017
%P 195-218
%V 21
%N 2
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00412/
%R 10.7155/jgaa.00412
%G en
%F JGAA_2017_21_2_a3
Sivan Altinakar; Gilles Caporossi; Alain Hertz. Symmetry Breaking Constraints for the Minimum Deficiency Problem. Journal of graph algorithms and applications, Tome 21 (2017) no. 2, pp. 195-218. doi: 10.7155/jgaa.00412

Cité par Sources :