SLIDE: A Useful Special Case of the CARDPATH Constraint - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2008

SLIDE: A Useful Special Case of the CARDPATH Constraint

Abstract

We study the CARDPATH constraint. This ensures a given constraint holds a number of times down a sequence of variables. We show that SLIDE, a special case of CARDPATH where the slid constraint must hold always, can be used to encode a wide range of sliding sequence constraints including CARDPATH itself. We con- sider how to propagate SLIDE and provide a complete propagator for CARDPATH. Since propagation is NP-hard in general, we identify special cases where propagation takes polynomial time. Our experi- ments demonstrate that using SLIDE to encode global constraints can be as efficient and effective as specialised propagators.
Fichier principal
Vignette du fichier
ecai08-slide.pdf (96.76 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00329876 , version 1 (13-10-2008)

Identifiers

  • HAL Id : lirmm-00329876 , version 1

Cite

Christian Bessiere, Emmanuel Hébrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh. SLIDE: A Useful Special Case of the CARDPATH Constraint. ECAI: European Conference on Artificial Intelligence, Jul 2008, Patras, Greece. pp.475-479. ⟨lirmm-00329876⟩
100 View
14 Download

Share

Gmail Facebook X LinkedIn More