CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishMost 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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
| Titolo: | Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems | |
| Autori: | ||
| Data di pubblicazione: | 2017 | |
| Rivista: | ||
| Handle: | http://hdl.handle.net/20.500.11770/133791 | |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/20.500.11770/133791
Copyright © 2021