{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T15:52:35Z","timestamp":1762271555971},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237850"},{"type":"electronic","value":"9783642237867"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-23786-7_27","type":"book-chapter","created":{"date-parts":[[2011,8,31]],"date-time":"2011-08-31T07:58:42Z","timestamp":1314777522000},"page":"340-355","source":"Crossref","is-referenced-by-count":5,"title":["Structural Tractability of Constraint Optimization"],"prefix":"10.1007","author":[{"given":"Gianluigi","family":"Greco","sequence":"first","affiliation":[]},{"given":"Francesco","family":"Scarcello","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"27_CR1","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":"27_CR2","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"},{"key":"27_CR3","unstructured":"Brafman, R.I., Rossi, F., Salvagnin, D., Venable, K.B., Walsh, T.: Finding the Next Solution in Constraint- and Preference-Based Knowledge Representation Formalisms. In: Proc. of KR 2010, pp. 425\u2013433 (2010)"},{"key":"27_CR4","unstructured":"Bulatov, A., Dalmau, V., Grohe, M., Marx, D.: Enumerating Homomorphism. In: Proc. of STACS 2009, pp. 231\u2013242 (2009)"},{"key":"27_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/11564751_15","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"H. Chen","year":"2005","unstructured":"Chen, H., Dalmau, V.: Beyond Hypertree Width: Decomposition Methods Without Decompositions. In: van Beek, P. (ed.) CP 2005. LNCS, vol.\u00a03709, pp. 167\u2013181. Springer, Heidelberg (2005)"},{"issue":"5","key":"27_CR6","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., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction problems. J. of Computer and System Sciences\u00a074(5), 721\u2013743 (2008)","journal-title":"J. of Computer and System Sciences"},{"key":"27_CR7","volume-title":"Constraint Processing","author":"R. Dechter","year":"2003","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)"},{"key":"27_CR8","unstructured":"Flerova, N., Dechter, R.: M best solutions over Graphical Models. In: Proc. of Constraint Reasoning and Graphical Structures, CP 2010 Workshop (2010)"},{"issue":"6","key":"27_CR9","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J. Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. Journal of the ACM\u00a049(6), 716\u2013752 (2002)","journal-title":"Journal of the ACM"},{"key":"27_CR10","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":"27_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-02930-1_2","volume-title":"Automata, Languages and Programming","author":"G. Gottlob","year":"2009","unstructured":"Gottlob, G., Greco, G., Scarcello, F.: Tractable Optimization Problems through Hypergraph-Based Structural Restrictions. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05556, pp. 16\u201330. Springer, Heidelberg (2009)"},{"issue":"2","key":"27_CR12","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":"1-2","key":"27_CR13","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1016\/S0304-3975(01)00108-6","volume":"270","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: Computing LOGCFL Certificates. Theoretical Computer Science\u00a0270(1-2), 761\u2013777 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"27_CR14","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"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Mikl\u00f3s, Z., Schwentick, T.: Generalized hypertree decompositions: $\\mbox{\\rm NP}$ -hardness and tractable variants. Journal of the ACM\u00a056(6) (2009)","DOI":"10.1145\/1568318.1568320"},{"key":"27_CR16","doi-asserted-by":"crossref","unstructured":"Greco, G., Scarcello, F.: The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability. In: Proc. of PODS 2010, pp. 327\u2013338 (2010)","DOI":"10.1145\/1807085.1807127"},{"key":"27_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/978-3-642-15396-9_21","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2010","author":"G. Greco","year":"2010","unstructured":"Greco, G., Scarcello, F.: Structural Tractability of Enumerating CSP Solutions. In: Cohen, D. (ed.) CP 2010. LNCS, vol.\u00a06308, pp. 236\u2013251. Springer, Heidelberg (2010)"},{"key":"27_CR18","unstructured":"Greco, G., Scarcello, F.: The tractability frontier of computing K best solutions. Techinical Report, University of Calabria (2011)"},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: Proc. of SODA 2006, pp. 289\u2013298 (2006)","DOI":"10.1145\/1109557.1109590"},{"key":"27_CR20","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM\u00a054(1) (2007)","DOI":"10.1145\/1206035.1206036"},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/11780991_13","volume-title":"Next Generation Information Technologies and Systems","author":"B. Kimelfeld","year":"2006","unstructured":"Kimelfeld, B., Sagiv, Y.: Incrementally computing ordered answers of acyclic conjunctive queries. In: Etzion, O., Kuflik, T., Motro, A. (eds.) NGITS 2006. LNCS, vol.\u00a04032, pp. 33\u201338. Springer, Heidelberg (2006)"},{"issue":"2","key":"27_CR22","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1006\/jcss.2000.1713","volume":"61","author":"P.G. Kolaitis","year":"1998","unstructured":"Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences\u00a061(2), 302\u2013332 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR23","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1287\/mnsc.18.7.401","volume":"18","author":"E.L. Lawler","year":"1972","unstructured":"Lawler, E.L.: A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science\u00a018, 401\u2013405 (1972)","journal-title":"Management Science"},{"key":"27_CR24","doi-asserted-by":"crossref","unstructured":"Marx, D.: Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. In: Proc. of STOC 2010, pp. 735\u2013744 (2010)","DOI":"10.1145\/1806689.1806790"},{"key":"27_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)"},{"key":"27_CR26","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)","DOI":"10.1109\/ICTAI.2008.109"},{"key":"27_CR27","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":"27_CR28","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors V: Excluding a planar graph. Journal of Combinatorial Theory, Series B\u00a041, 92\u2013114 (1986)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"27_CR29","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W.L. Ruzzo","year":"1980","unstructured":"Ruzzo, W.L.: Tree-size bounded alternation. Journal of Cumputer and System Sciences\u00a021, 218\u2013235 (1980)","journal-title":"Journal of Cumputer and System Sciences"},{"key":"27_CR30","unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: Proc. of VLDB 1981, pp. 82\u201394 (1981)"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2013 CP 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23786-7_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T16:37:03Z","timestamp":1560530223000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23786-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237850","9783642237867"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23786-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}