SLIDE: A Useful Special Case of the CARDPATH Constraint

Simple item page
dc.creatorBessiere, Christian
dc.creatorHebrard, Emmanuel
dc.creatorHnich, Brahim
dc.creatorKiziltan, Zeynep
dc.creatorWalsh, Toby
dc.date2009-03-03
dc.date.accessioned2026-07-07T12:48:37Z
dc.date.available2026-07-07T12:48:37Z
dc.descriptionWe 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 consider 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 experiments demonstrate that using SLIDE to encode global constraints can be as efficient and effective as specialised propagators.
dc.description18th European Conference on Artificial Intelligence
dc.identifierhttps://arxiv.org/abs/0903.0471
dc.identifierhttp://arxiv.org/abs/0903.0471
dc.identifierECAI 2008: 475-479
dc.identifierdoi:10.3233/978-1-58603-891-5-475
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/222118
dc.subjectArtificial Intelligence
dc.subjectComputational Complexity
dc.subjectI.2.4
dc.titleSLIDE: A Useful Special Case of the CARDPATH Constraint
dc.typetext

Files

Collections

arXiv