کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950637 | 1440714 | 2017 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
ترجمه فارسی عنوان
استراتژی های حریصانه و جزایر بزرگ ترقیابی برای پرسش های مونتاژ و مسائل رضایت محدود
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Most structural decomposition methods can be characterized through hypergraph games that are variations of the Robber and Cops graph game that characterizes the notion of treewidth. Decomposition trees correspond to monotone winning strategies of the cops, where the escape space of the robber on the hypergraph is shrunk monotonically. Cops using non-monotonic strategies are more powerful, but such strategies do not correspond to valid decompositions, in general. The paper provides a general way to exploit the power of non-monotonic strategies, by allowing a “greedy” form of non-monotonicity. It is shown that deciding the existence of a (non-monotone) greedy winning strategy (and compute one, if any) is tractable. Moreover, from greedy strategies we can compute valid decomposition trees efficiently. As a consequence, we are able to add power to structural methods and to obtain larger islands of tractability, such as the one based on the new notion of greedy hypertree decomposition.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 252, February 2017, Pages 201-220
Journal: Information and Computation - Volume 252, February 2017, Pages 201-220
نویسندگان
Gianluigi Greco, Francesco Scarcello,