Periodic Constraint Satisfaction Problems: Tractable Subclasses |
| |
Authors: | Email author" target="_blank">Hubie?ChenEmail author |
| |
Affiliation: | (1) Departament de Tecnologia, Universitat Pompeu Fabra, Barcelona, Spain |
| |
Abstract: | We study a generalization of the constraint satisfaction problem (CSP), the periodic constraint satisfaction problem. An input instance of the periodic CSP is a finite set of generating constraints over a structured variable set that implicitly specifies a larger, possibly infinite set of constraints; the problem is to decide whether or not the larger set of constraints has a satisfying assignment. This model is natural for studying constraint networks consisting of constraints obeying a high degree of regularity or symmetry. Our main contribution is the identification of two broad polynomial-time tractable subclasses of the periodic CSP. |
| |
Keywords: | periodic problems polynomial-time algorithms |
本文献已被 SpringerLink 等数据库收录! |