{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:20:27Z","timestamp":1743117627856,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029295"},{"type":"electronic","value":"9783642029301"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-02930-1_2","type":"book-chapter","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T11:05:04Z","timestamp":1246532704000},"page":"16-30","source":"Crossref","is-referenced-by-count":17,"title":["Tractable Optimization Problems through Hypergraph-Based Structural Restrictions"],"prefix":"10.1007","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[]},{"given":"Gianluigi","family":"Greco","sequence":"additional","affiliation":[]},{"given":"Francesco","family":"Scarcello","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"2167","DOI":"10.1016\/j.ejc.2007.04.013","volume":"28","author":"I. Adler","year":"2007","unstructured":"Adler, I., Gottlob, G., Grohe, M.: Hypertree-Width and Related Hypergraph Invariants. European Journal of Combinatorics\u00a028, 2167\u20132181 (2007)","journal-title":"European Journal of Combinatorics"},{"issue":"3","key":"2_CR2","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1145\/2402.322389","volume":"30","author":"C. Beeri","year":"1983","unstructured":"Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. Journal of the ACM\u00a030(3), 479\u2013513 (1983)","journal-title":"Journal of the ACM"},{"issue":"4","key":"2_CR3","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1137\/0210059","volume":"10","author":"P.A. Bernstein","year":"1981","unstructured":"Bernstein, P.A., Goodman, N.: The power of natural semijoins. SIAM Journal on Computing\u00a010(4), 751\u2013771 (1981)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"2_CR4","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1023\/A:1026441215081","volume":"4","author":"S. Bistarelli","year":"1999","unstructured":"Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., Fargier, H.: Semiring-Based CSPs and Valued CSPs: Frameworks, Properties,and Comparison. Constraints\u00a04(3), 199\u2013240 (1999)","journal-title":"Constraints"},{"issue":"6","key":"2_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Fomin, F.V.: A Linear-Time Algorithm for Finding Tree Decompositions of Small Treewidth. SIAM Journal on Computing\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","first-page":"56","volume-title":"Database Theory - ICDT \u201997","year":"1996","unstructured":"Chekuri, C., Rajaraman, A.: Conjunctive Query Containment Revisited. MFPS 1985\u00a0239(2), 211\u2013229 (2000); Preliminary version in: Schwentick, T., Suciu, D. (eds.): ICDT 2007. LNCS, vol.\u00a04353, pp. 211\u2013229. Springer, Heidelberg (2007); Afrati, F.N., Kolaitis, P.G. (eds.): ICDT 1997. LNCS, vol.\u00a01186, pp. 56\u201370. Springer, Heidelberg (1996) (Full version)"},{"issue":"5","key":"2_CR7","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1016\/j.jcss.2007.08.001","volume":"74","author":"D.A. Cohen","year":"2008","unstructured":"Cohen, D.A., Jeavons, P.G., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction problems. Journal of Computer and System Sciences\u00a074(5), 721\u2013743 (2008)","journal-title":"Journal of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Computing pure nash equilibria in graphical games via markov random fields. In: Proc. of ACM EC 2006, pp. 91\u201399 (2006)","key":"2_CR8","DOI":"10.1145\/1134707.1134718"},{"issue":"3","key":"2_CR9","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/2402.322390","volume":"30","author":"R. Fagin","year":"1983","unstructured":"Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. J. ACM\u00a030(3), 514\u2013550 (1983)","journal-title":"J. ACM"},{"unstructured":"de Givry, S., Schiex, T., Verfaillie, G.: Exploiting Tree Decomposition and Soft Local Consistency In Weighted CSP. In: Proc. of AAAI 2006 (2006)","key":"2_CR10"},{"key":"2_CR11","volume-title":"Constraint Processing","author":"R. Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)"},{"issue":"1-3","key":"2_CR12","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0004-3702(92)90004-H","volume":"58","author":"E.C. Freuder","year":"1992","unstructured":"Freuder, E.C., Wallace, R.J.: Partial Constraint Satisfaction. Artificial Intelligence\u00a058(1-3), 21\u201370 (1992)","journal-title":"Artificial Intelligence"},{"doi-asserted-by":"crossref","unstructured":"Gottlob, G., Greco, G.: On the complexity of combinatorial auctions: structured item graphs and hypertree decomposition. In: Proc. EC 2007, pp. 152\u2013161 (2007) (full version currently available as Technical Report, University of Calabria)","key":"2_CR13","DOI":"10.1145\/1250910.1250934"},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1613\/jair.1683","volume":"24","author":"G. Gottlob","year":"2005","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: Pure Nash Equilibria: Hard and Easy Games. Journal of Artificial Intelligence Research\u00a024, 357\u2013406 (2005)","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"2","key":"2_CR15","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G. Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural CSP decomposition methods. Artificial Intelligence\u00a0124(2), 243\u2013282 (2000)","journal-title":"Artificial Intelligence"},{"issue":"3","key":"2_CR16","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/382780.382783","volume":"48","author":"G. Gottlob","year":"2001","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. Journal of the ACM\u00a048(3), 431\u2013498 (2001)","journal-title":"Journal of the ACM"},{"unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Advanced parallel algorithms for processing acyclic conjunctive queries, rules, and constraints. In: Proc. of SEKE 2000, pp. 167\u2013176 (2000)","key":"2_CR17"},{"issue":"3","key":"2_CR18","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. J. of Computer and System Sciences\u00a064(3), 579\u2013627 (2002)","journal-title":"J. of Computer and System Sciences"},{"issue":"4","key":"2_CR19","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1016\/S0022-0000(03)00030-8","volume":"66","author":"G. Gottlob","year":"2003","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. J. of Computer and System Sciences\u00a066(4), 775\u2013808 (2003)","journal-title":"J. of Computer and System Sciences"},{"doi-asserted-by":"crossref","unstructured":"Gottlob, G., Mikl\u00f3s, Z., Schwentick, T.: Generalized hypertree decompositions: NP-hardness and tractable variants. In: Proc. of PODS 2007, pp. 13\u201322 (2007)","key":"2_CR20","DOI":"10.1145\/1265530.1265533"},{"unstructured":"Gottlob, G., Pichler, R., Wei, F.: Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning. In: Proc. of AAAI 2006 (2006)","key":"2_CR21"},{"unstructured":"Greco, G., Scarcello, F.: Non-Binary Constraints and Optimal Dual-Graph Representations. In: Proc. of IJCAI 2003, pp. 227\u2013232 (2003)","key":"2_CR22"},{"doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: Proc. of SODA 2006, Miami, Florida, USA, pp. 289\u2013298 (2006)","key":"2_CR23","DOI":"10.1145\/1109557.1109590"},{"issue":"1-2","key":"2_CR24","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.artint.2005.04.004","volume":"166","author":"K. Kask","year":"2005","unstructured":"Kask, K., Dechter, R., Larrosa, J., Dechter, A.: Unifying tree decompositions for reasoning in graphical models. Artificial Intelligence\u00a0166(1-2), 165\u2013193 (2005)","journal-title":"Artificial Intelligence"},{"key":"2_CR25","volume-title":"Handbook of Constraint Programming","author":"P. Meseguer","year":"2006","unstructured":"Meseguer, P., Rossi, F., Schiex, T.: Soft Constraints. In: Handbook of Constraint Programming. Elsevier, Amsterdam (2006)"},{"doi-asserted-by":"crossref","unstructured":"Ndiaye, S., J\u00e9gou, P., Terrioux, C.: Extending to Soft and Preference Constraints a Framework for Solving Efficiently Structured Problems. In: Proc. of ICTAI 2008, pp. 299\u2013306 (2008)","key":"2_CR26","DOI":"10.1109\/ICTAI.2008.109"},{"issue":"4","key":"2_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"Omer Reingold","year":"2008","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. Journal of the ACM\u00a055(4) (2008)","journal-title":"Journal of the ACM"},{"key":"2_CR28","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N. Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors III: Planar tree-width. Journal of Combinatorial Theory, Series B\u00a036, 49\u201364 (1984)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-540-92800-3_7","volume-title":"Complexity of Constraints","author":"F. Scarcello","year":"2008","unstructured":"Scarcello, F., Gottlob, G., Greco, G.: Uniform Constraint Satisfaction Problems and Database Theory. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints. LNCS, vol.\u00a05250, pp. 156\u2013195. Springer, Heidelberg (2008)"},{"unstructured":"Schiex, T., Fargier, H., Verfaillie, G.: Valued Constraint Satisfaction Problems: Hard and Easy Problems. In: Proc. of IJCAI 1995, pp. 631\u2013639 (1995)","key":"2_CR30"},{"issue":"3","key":"2_CR31","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"R.E. Tarjan","year":"1984","unstructured":"Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing\u00a013(3), 566\u2013579 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR32","volume-title":"Foundations of Constraint Satisfaction","author":"E. Tsang","year":"1993","unstructured":"Tsang, E.: Foundations of Constraint Satisfaction. Academic Press, London (1993)"},{"key":"2_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/978-3-540-45193-8_48","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"C. Terrioux","year":"2003","unstructured":"Terrioux, C., J\u2019egou, P.: Bounded Backtracking for the Valued Constraint Satisfaction Problems. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 709\u2013723. Springer, Heidelberg (2003)"},{"unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: Proc. of VLDB 1981, pp. 82\u201394 (1981)","key":"2_CR34"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02930-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T01:49:30Z","timestamp":1558403370000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02930-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029295","9783642029301"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02930-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}