Propagation via Kernelization: The Vertex Cover Constraint

Clément Carbonnel 1 Emmanuel Hébrard 1
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
Abstract : The technique of kernelization consists in extracting, from an instance of a problem, an essentially equivalent instance whose size is bounded in a parameter k. Besides being the basis for efficient param-eterized algorithms, this method also provides a wealth of information to reason about in the context of constraint programming. We study the use of kernelization for designing propagators through the example of the Vertex Cover constraint. Since the classic kernelization rules often correspond to dominance rather than consistency, we introduce the notion of " loss-less " kernel. While our preliminary experimental results show the potential of the approach, they also show some of its limits. In particular, this method is more effective for vertex covers of large and sparse graphs, as they tend to have, relatively, smaller kernels.
Type de document :
Communication dans un congrès
Michel Rueher. The 22nd International Conference on Principles and Practice of Constraint Programming, Sep 2016, Toulouse, France. Lecture Notes in Computer Science, 9892, pp.147 - 156, 2016, Principles and Practice of Constraint Programming. 〈10.1007/978-3-319-44953-1_10〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.laas.fr/hal-01459870
Contributeur : Emmanuel Hebrard <>
Soumis le : mardi 7 février 2017 - 15:00:51
Dernière modification le : mercredi 28 février 2018 - 10:23:14
Document(s) archivé(s) le : lundi 8 mai 2017 - 14:47:41

Fichiers

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Clément Carbonnel, Emmanuel Hébrard. Propagation via Kernelization: The Vertex Cover Constraint. Michel Rueher. The 22nd International Conference on Principles and Practice of Constraint Programming, Sep 2016, Toulouse, France. Lecture Notes in Computer Science, 9892, pp.147 - 156, 2016, Principles and Practice of Constraint Programming. 〈10.1007/978-3-319-44953-1_10〉. 〈hal-01459870〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

13