{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T16:53:32Z","timestamp":1744217612954,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030300470"},{"type":"electronic","value":"9783030300487"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-30048-7_12","type":"book-chapter","created":{"date-parts":[[2019,9,22]],"date-time":"2019-09-22T19:03:06Z","timestamp":1569178986000},"page":"195-212","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Join-Based Hybrid Parameter for Constraint Satisfaction"],"prefix":"10.1007","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,23]]},"reference":[{"issue":"13","key":"12_CR1","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.14778\/2733004.2733017","volume":"7","author":"R Ahmed","year":"2014","unstructured":"Ahmed, R., Sen, R., Poess, M., Chakkappen, S.: Of snowstorms and bushy trees. Proc. VLDB Endowment 7(13), 1452\u20131461 (2014)","journal-title":"Proc. VLDB Endowment"},{"unstructured":"Alekhnovich, M., Razborov, A.A.: Satisfiability, branch-width and Tseitin tautologies. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 593\u2013603 (2002)","key":"12_CR2"},{"issue":"4","key":"12_CR3","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1137\/110859440","volume":"42","author":"A Atserias","year":"2013","unstructured":"Atserias, A., Grohe, M., Marx, D.: Size bounds and query plans for relational joins. SIAM J. Comput. 42(4), 1737\u20131767 (2013)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"12_CR4","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"AA Bulatov","year":"2005","unstructured":"Bulatov, A.A., Jeavons, P., Krokhin, A.A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/978-3-642-23786-7_14","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2011","author":"DA Cohen","year":"2011","unstructured":"Cohen, D.A., Cooper, M.C., Green, M.J., Marx, D.: On guaranteeing polynomially bounded search tree size. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 160\u2013171. Springer, Heidelberg (2011). \n                      https:\/\/doi.org\/10.1007\/978-3-642-23786-7_14"},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.ic.2018.09.013","volume":"264","author":"DA Cohen","year":"2019","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G., Zivny, S.: Binary constraint satisfaction problems defined by excluded topological minors. Inf. Comput. 264, 12\u201331 (2019)","journal-title":"Inf. Comput."},{"key":"12_CR7","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/j.artint.2016.02.001","volume":"234","author":"MC Cooper","year":"2016","unstructured":"Cooper, M.C., Duchein, A., El Mouelhi, A., Escamocher, G., Terrioux, C., Zanuttini, B.: Broken triangles: From value merging to a tractable class of general-arity constraint satisfaction problems. Artif. Intell. 234, 196\u2013218 (2016)","journal-title":"Artif. Intell."},{"unstructured":"Cooper, M.C., Zivny, S.: Hybrid tractable classes of constraint problems. In: The Constraint Satisfaction Problem, volume 7 of Dagstuhl Follow-Ups, pp. 113\u2013135. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017)","key":"12_CR8"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1613\/jair.167","volume":"2","author":"P David","year":"1995","unstructured":"David, P.: Using pivot consistency to decompose and solve functional CSPs. J. Artif. Intell. Res. 2, 447\u2013474 (1995)","journal-title":"J. Artif. Intell. Res."},{"unstructured":"Deville, Y., Van Hentenryck, P.: An efficient arc consistency algorithm for a class of CSP problems. In: Proceedings of the 12th International Joint Conference on Artificial Intelligence, Sydney, Australia, pp. 325\u2013330, 24\u201330 August 1991","key":"12_CR10"},{"key":"12_CR11","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"Reinhard Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory: GTM, 4th edn., vol. 173. Springer, Heidelberg (2017). \n                      https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"key":"12_CR12","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"Rodney G. Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013). \n                      https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"doi-asserted-by":"crossref","unstructured":"Fischl, W., Gottlob, G., Pichler, R.: General and fractional hypertree decompositions: hard and easy cases. In: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Houston, TX, USA, pp. 17\u201332. ACM, 10\u201315 June 2018","key":"12_CR13","DOI":"10.1145\/3196959.3196962"},{"doi-asserted-by":"publisher","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science, vol. XIV. An EATCS Series. Springer, Berlin (2006). \n                      https:\/\/doi.org\/10.1007\/3-540-29953-X","key":"12_CR14","DOI":"10.1007\/3-540-29953-X"},{"issue":"3","key":"12_CR15","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. Comput. Syst. Sci. 64(3), 579\u2013627 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"12_CR16","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1093\/comjnl\/bxm056","volume":"51","author":"G Gottlob","year":"2006","unstructured":"Gottlob, G., Szeider, S.: Fixed-parameter algorithms for artificial intelligence, constraint satisfaction, and database problems. Comput. J. 51(3), 303\u2013325 (2006)","journal-title":"Comput. J."},{"issue":"4","key":"12_CR17","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/637411.637428","volume":"31","author":"M Grohe","year":"2002","unstructured":"Grohe, M.: Parameterized complexity for the database theorist. SIGMOD Rec. 31(4), 86\u201396 (2002)","journal-title":"SIGMOD Rec."},{"issue":"1","key":"12_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1206035.1206036","volume":"54","author":"M Grohe","year":"2007","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1), 1\u201324 (2007)","journal-title":"J. ACM"},{"unstructured":"Grohe, M.: Logic, graphs, and algorithms. In: Logic and Automata: History and Perspectives. Texts in Logic and Games, vol. 2, pp. 357\u2013422. Amsterdam University Press (2007)","key":"12_CR19"},{"unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. ACM Trans. Algorithms 11(1), 4:1\u20134:20 (2014). \n                      http:\/\/doi.acm.org\/10.1145\/2636918","key":"12_CR20"},{"issue":"4","key":"12_CR21","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Ioannidis, Y.E., Kang, Y.C.: Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization. In: Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, pp. 168\u2013177. ACM Press (1991)","key":"12_CR22","DOI":"10.1145\/119995.115813"},{"unstructured":"Khamis, M.A., Ngo, H.Q., Rudra, A.: FAQ: questions asked frequently. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, pp. 3\u201328. ACM, 26 June\u201301 July 2016","key":"12_CR23"},{"unstructured":"Khamis, M.A., Ngo, H.Q., Suciu, D.: What do Shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, pp. 429\u2013444. ACM, 14\u201319 May 2017","key":"12_CR24"},{"issue":"2","key":"12_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1721837.1721845","volume":"6","author":"D\u00e1niel Marx","year":"2010","unstructured":"Marx, D.: Approximating fractional hypertree width. ACM Trans. Algorithms 6(2), 17 (2010). Art. 29","journal-title":"ACM Transactions on Algorithms"},{"issue":"3","key":"12_CR26","doi-asserted-by":"publisher","first-page":"444","DOI":"10.1007\/s00224-009-9248-9","volume":"48","author":"D Marx","year":"2011","unstructured":"Marx, D.: Tractable structures for constraint satisfaction with truth tables. Theory Comput. Syst. 48(3), 444\u2013464 (2011)","journal-title":"Theory Comput. Syst."},{"issue":"6","key":"12_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2535926","volume":"60","author":"D\u00e1niel Marx","year":"2013","unstructured":"Marx, D.: Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM 60(6), 42:1\u201342:51 (2013)","journal-title":"Journal of the ACM"},{"issue":"4","key":"12_CR28","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1080\/0952813X.2012.721138","volume":"25","author":"W Naanaa","year":"2013","unstructured":"Naanaa, W.: Unifying and extending hybrid tractable classes of csps. J. Exp. Theor. Artif. Intell. 25(4), 407\u2013424 (2013)","journal-title":"J. Exp. Theor. Artif. Intell."},{"issue":"1","key":"12_CR29","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"Neil Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. excluding a forest. J. Combin. Theory Ser. B 35(1), 39\u201361 (1983)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"3","key":"12_CR30","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"Neil Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"volume-title":"Handbook of Constraint Programming","year":"2006","unstructured":"Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier, New York (2006)","key":"12_CR31"},{"issue":"2","key":"12_CR32","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"PD Seymour","year":"1994","unstructured":"Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217\u2013241 (1994)","journal-title":"Combinatorica"},{"unstructured":"Yannakakis, M.: Algorithms for acyclic database schemes. In: Proceedings of 7th International Conference Very Large Data Bases, Cannes, France, pp. 81\u201394. IEEE Computer Society, 9\u201311 September 1981","key":"12_CR33"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-30048-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T22:04:03Z","timestamp":1569449043000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-30048-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030300470","9783030300487"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-30048-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"23 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Principles and Practice of Constraint Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Stamford, CT","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 September 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 October 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cp2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cp2019.a4cp.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"118","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"39% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}