کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430100 | 687798 | 2012 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Enumerating homomorphisms Enumerating homomorphisms](/preview/png/430100.png)
The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.
► We study the problem of enumerating all solutions of a CSP with polynomial delay.
► We focus on structural or left-hand restrictions.
► We provide evidence that a complete characterization is hard.
► We obtain nontrivial cases where enumeration can be done with polynomial delay.
Journal: Journal of Computer and System Sciences - Volume 78, Issue 2, March 2012, Pages 638–650