{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:17:31Z","timestamp":1725585451413},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642215803"},{"type":"electronic","value":"9783642215810"}],"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-21581-0_11","type":"book-chapter","created":{"date-parts":[[2011,6,10]],"date-time":"2011-06-10T09:30:19Z","timestamp":1307698219000},"page":"120-133","source":"Crossref","is-referenced-by-count":10,"title":["Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight"],"prefix":"10.1007","author":[{"given":"Nadia","family":"Creignou","sequence":"first","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Olive","sequence":"additional","affiliation":[]},{"given":"Johannes","family":"Schmidt","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/978-3-540-74915-8_18","volume-title":"Computer Science Logic","author":"G. Bagan","year":"2007","unstructured":"Bagan, G., Durand, A., Grandjean, E.: On acyclic conjunctive queries and constant delay enumeration. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol.\u00a04646, pp. 208\u2013222. Springer, Heidelberg (2007)"},{"key":"11_CR2","unstructured":"Barg, A.: Complexity issues in coding theory. Electronic Colloquium on Computational Complexity (ECCC) 4(46) (1997)"},{"issue":"3","key":"11_CR3","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1023\/B:CONS.0000036045.82829.94","volume":"9","author":"D.A. Cohen","year":"2004","unstructured":"Cohen, D.A.: Tractable decision for a constraint language implies tractable search. Constraints\u00a09(3), 219\u2013229 (2004)","journal-title":"Constraints"},{"issue":"6","key":"11_CR4","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1051\/ita\/1997310604991","volume":"31","author":"N. Creignou","year":"1997","unstructured":"Creignou, N., H\u00e9brard, J.-J.: On generating all solutions of generalized satisfiability problems. Theoretical Informatics and Applications\u00a031(6), 499\u2013511 (1997)","journal-title":"Theoretical Informatics and Applications"},{"volume-title":"Complexity of Constraints","year":"2008","series-title":"Lecture Notes in Computer Science","key":"11_CR5","unstructured":"Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.): Complexity of Constraints. LNCS, vol.\u00a05250. Springer, Heidelberg (2008)"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Creignou, N., Schnoor, H., Schnoor, I.: Nonuniform boolean constraint satisfaction problems with cardinality constraint. ACM Trans. Comput. Log.\u00a011(4) (2010)","DOI":"10.1145\/1805950.1805954"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Creignou, N., Vollmer, H.: Boolean constraint satisfaction problems: When does Post\u2019s lattice help? In: Creignou, et al [5], pp. 3\u201337","DOI":"10.1007\/978-3-540-92800-3_2"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Hagen, M.: Lower bounds for three algorithms for transversal hypergraph generation. Discrete Applied Mathematics (2009)","DOI":"10.1016\/j.dam.2008.10.004"},{"key":"11_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P.G. Jeavons","year":"1998","unstructured":"Jeavons, P.G.: On the algebraic structure of combinatorial problems. Theoretical Computer Science\u00a0200, 185\u2013204 (1998)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"11_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Process. Lett.\u00a027(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Jonsson, P., Nordh, G.: Introduction to the maximum solution problem. In: Creignou, et al [5], pp. 255\u2013282","DOI":"10.1007\/978-3-540-92800-3_10"},{"key":"11_CR12","first-page":"11","volume-title":"Proceedings 29th Symposium on Theory of Computing","author":"S. Khanna","year":"1997","unstructured":"Khanna, S., Sudan, M., Williamson, D.: A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. In: Proceedings 29th Symposium on Theory of Computing, pp. 11\u201320. ACM Press, New York (1997)"},{"issue":"1","key":"11_CR13","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(91)90081-C","volume":"88","author":"S. Khuller","year":"1991","unstructured":"Khuller, S., Vazirani, V.V.: Planar graph coloring is not self-reducible, assuming P\u2260NP. Theoretical Computer Science\u00a088(1), 183\u2013189 (1991)","journal-title":"Theoretical Computer Science"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","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. 141\u2013152. Springer, Heidelberg (2006)"},{"issue":"4-5","key":"11_CR15","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.is.2008.01.002","volume":"33","author":"B. Kimelfeld","year":"2008","unstructured":"Kimelfeld, B., Sagiv, Y.: Efficiently enumerating results of keyword search over data graphs. Inf. Syst.\u00a033(4-5), 335\u2013359 (2008)","journal-title":"Inf. Syst."},{"key":"11_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/978-3-540-70575-8_54","volume-title":"Automata, Languages and Programming","author":"A.A. Krokhin","year":"2008","unstructured":"Krokhin, A.A., Marx, D.: On the hardness of losing weight. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 662\u2013673. Springer, Heidelberg (2008)"},{"key":"11_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-540-27810-8_23","volume-title":"Algorithm Theory - SWAT 2004","author":"K. Makino","year":"2004","unstructured":"Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 260\u2013272. Springer, Heidelberg (2004)"},{"issue":"2","key":"11_CR18","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00037-005-0195-9","volume":"14","author":"D. Marx","year":"2005","unstructured":"Marx, D.: Parameterized complexity of constraint satisfaction problems. Computational Complexity\u00a014(2), 153\u2013183 (2005)","journal-title":"Computational Complexity"},{"key":"11_CR19","first-page":"216","volume-title":"Proccedings 10th Symposium on Theory of Computing","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proccedings 10th Symposium on Theory of Computing, pp. 216\u2013226. ACM Press, New York (1978)"},{"key":"11_CR20","unstructured":"Schmidt, J.: Enumeration: Algorithms and complexity. Preprint (2009), http:\/\/www.thi.uni-hannover.de\/fileadmin\/forschung\/arbeiten\/schmidt-da.pdf"},{"key":"11_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1007\/978-3-540-70918-3_59","volume-title":"STACS 2007","author":"H. Schnoor","year":"2007","unstructured":"Schnoor, H., Schnoor, I.: Enumerating all solutions for constraint satisfaction problems. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 694\u2013705. Springer, Heidelberg (2007)"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Schnoor, H., Schnoor, I.: Partial polymorphisms and constraint satisfaction problems. In: Creignou, et al [5], pp. 229\u2013254","DOI":"10.1007\/978-3-540-92800-3_9"},{"key":"11_CR23","unstructured":"Schnorr, C.P.: Optimal algorithms for self-reducible problems. In: International Conference on Automata, Languages and Programming, pp. 322\u2013337 (1976)"},{"key":"11_CR24","unstructured":"Strozecki, Y.: Enumeration complexity and matroid decomposition. Phd thesis (2010)"},{"key":"11_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/3-540-55719-9_88","volume-title":"Automata, Languages and Programming","author":"V. Vazirani","year":"1992","unstructured":"Vazirani, V., Yannakakis, M.: Suboptimal cuts: Their enumeration, weight and number. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 366\u2013377. Springer, Heidelberg (1992)"},{"issue":"3","key":"11_CR26","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00453-009-9284-5","volume":"56","author":"L.-P. Yeh","year":"2010","unstructured":"Yeh, L.-P., Wang, B.-F., Su, H.-H.: Efficient algorithms for the problems of enumerating cuts by non-decreasing weights. Algorithmica\u00a056(3), 297\u2013312 (2010)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21581-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T12:21:00Z","timestamp":1560255660000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21581-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642215803","9783642215810"],"references-count":26,"URL":"http:\/\/dx.doi.org\/10.1007\/978-3-642-21581-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}
