{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:30:52Z","timestamp":1725514252788},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540681052"},{"type":"electronic","value":"9783540681113"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-68111-3_27","type":"book-chapter","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T16:27:12Z","timestamp":1211992032000},"page":"249-258","source":"Crossref","is-referenced-by-count":6,"title":["JaCk-SAT: A New Parallel Scheme to Solve the Satisfiability Problem (SAT) Based on Join-and-Check"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Singer","sequence":"first","affiliation":[]},{"given":"Anthony","family":"Monnet","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"unstructured":"http:\/\/www.cs.ubc.ca\/~hoos\/SATLIB\/","key":"27_CR1"},{"doi-asserted-by":"crossref","unstructured":"Amir, E., McIllraith, S.: Solving Satisfiability using Decomposition and the Most Constrained Subproblem. In: IJCAI 2001 Workshop on Distributed Constraint Reasoning, online http:\/\/www.cs.berkeley.edu\/~eyal\/paper.html","key":"27_CR2","DOI":"10.1016\/S1571-0653(04)00331-2"},{"key":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1007\/11546924_60","volume-title":"Database and Expert Systems Applications","author":"M. Bamha","year":"2005","unstructured":"Bamha, M.: An optimal skew-insensitive join and multi-join algorithm for distributed architecture. In: Andersen, K.V., Debenham, J., Wagner, R. (eds.) DEXA 2005. LNCS, vol.\u00a03588, pp. 616\u2013625. Springer, Heidelberg (2005)"},{"unstructured":"Bayardo Jr., R.J., Pehousek, J.D.: Counting Models Using Connected Components. In: Proc. 17th. Nat. Conf. on AI (AAAI 2000) (2000)","key":"27_CR4"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"201","DOI":"10.3233\/SAT190022","volume":"2","author":"A. Biere","year":"2006","unstructured":"Biere, A., Sinz, C.: Decomposing Sat Problems into Connected Components. Journal on Satisfiability, Boolean Modeling and Computation\u00a02, 201\u2013208 (2006)","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"27_CR6","series-title":"Lecture Notes in Computer Science","volume-title":"Theory and Applications of Satisfiability Testing","author":"P. Bjesse","year":"2004","unstructured":"Bjesse, P., Kukula, J., Damiano, R., Stanion, T., Zhu, Y.: Diagnosis with Tree Decomposition. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, Springer, Heidelberg (2004)"},{"unstructured":"Bodlaender, H.: A Tourist Guide through Treewidth. Acta Cybernetica 11 (1993)","key":"27_CR7"},{"unstructured":"Darwiche, A.: Compiling knowledge into decomposable negation normal form. In: Proc. of 15th. IJCAI, pp. 284\u2013289 (1999)","key":"27_CR8"},{"doi-asserted-by":"crossref","unstructured":"Davis, M., Logeman, G., Loveland, D.: A machine program for Theorem Proving. Com. of the ACM\u00a05(7) (1962)","key":"27_CR9","DOI":"10.1145\/368273.368557"},{"key":"27_CR10","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/3-540-45653-8_27","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"A. Val del","year":"2001","unstructured":"del Val, A.: Simplifying Binary Propositional Theories into Connected Components Twice as Fast. In: Nieuwenhuis, R., Voronkov, A. (eds.) LPAR 2001. LNCS (LNAI), vol.\u00a02250, pp. 389\u2013403. Springer, Heidelberg (2001)"},{"key":"27_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1007\/978-3-540-24605-3_36","volume-title":"Theory and Applications of Satisfiability Testing","author":"G. Dequen","year":"2004","unstructured":"Dequen, G., Dubois, O.: kcnfs: an efficient solver for random k-SAT formulae. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 486\u2013501. Springer, Heidelberg (2004)"},{"doi-asserted-by":"crossref","unstructured":"Durairaj, V., Kalla, P.: Exploiting Hypergraph Partitioning for Efficient Boolean Satisfiability. In: Proc. 9th. IEEE Int. High Level Design Validation and Test Workshp, pp. 141\u2013146 (2004)","key":"27_CR12","DOI":"10.1109\/HLDVT.2004.1431257"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","first-page":"2005","volume-title":"Theory and Applications of Satisfiability Testing","author":"R. Gummadi","year":"2005","unstructured":"Gummadi, R., Narayanaswamy, N.S., Venkatakrishnan, R.: Algorithms for Satisfiability Using Independent Sets of Variables. In: H. Hoos, H., Mitchell, D.G. (eds.) SAT 2004. LNCS, vol.\u00a03542, p. 2005. Springer, Heidelberg (2005)"},{"issue":"2-4","key":"27_CR14","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1504\/IJCSE.2005.009703","volume":"1","author":"Z. Habbas","year":"2005","unstructured":"Habbas, Z., Krajecki, M., Singer, D.: Decomposition Techniques for Parallel Resolution of Constraint Satisfaction Problems in Shared Memory: a Comparative Study. Int. Jour. of Computational Science and Engineering (IJCSE)\u00a01(2-4), 192\u2013206 (2005)","journal-title":"Int. Jour. of Computational Science and Engineering (IJCSE)"},{"unstructured":"Herwig, P.R.: Decomposing satisfiability problems. Master\u2019s Thesis, Delft University of Technology (2006)","key":"27_CR15"},{"unstructured":"Heule, M., Kullmann, O.: Decomposing clause-sets: Integrating DLL algorithms, tree decompositions and hypergraph cuts for variable and clause-based graph representations of CNF\u2019s. TR. CSR 2-2006, Univ. Wales Swansea (2006)","key":"27_CR16"},{"doi-asserted-by":"crossref","unstructured":"Hicks, I.V., Koster, A., Kolotoglu, E.: Branch and Tree Decomposition Techniques for Discrete Optimization. TutORials in O.R., Informs (2005)","key":"27_CR17","DOI":"10.1287\/educ.1053.0017"},{"key":"27_CR18","volume-title":"Multilevel Optimization Methods for VLSI, ch.6","author":"G. Karypis","year":"2002","unstructured":"Karypis, G.: Multilevel Hypergraph partitionning. In: Cong, J., Shinnerl, J. (eds.) Multilevel Optimization Methods for VLSI, ch.6, Kluwer Ac. Pub, Dordrecht (2002)"},{"key":"27_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"Theory and Applications of Satisfiability Testing","author":"S. Khurshid","year":"2004","unstructured":"Khurshid, S., Marinov, D., Shlyakhter, I., Jackson, D.: A Case for Efficient Solution Enumeration. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, Springer, Heidelberg (2004)"},{"unstructured":"Li, W., Van Beek, P.: Guiding Real-World Sat Solving with Dynamic Hypergraph Separator Decomposition. In: Proc. 16th. IEEE Int. Conf. on Tools for AI (ICTAI 2004) (2004)","key":"27_CR20"},{"unstructured":"Marques Silva, J., Oliveira, A.: Improving Satisfiability Algorithms with Dominance and Partitioning. In: Int. Workshop on Logic Synthesis (IWLS) (1997)","key":"27_CR21"},{"issue":"1","key":"27_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/128762.128764","volume":"24","author":"P. Mishra","year":"1992","unstructured":"Mishra, P., Eich, M.H.: Join Processing in Relational Databases. ACM Computing Surveys\u00a024(1), 63\u2013113 (1992)","journal-title":"ACM Computing Surveys"},{"unstructured":"Monnet, A.: JaCk-SAT: un nouvel algorithme de r\u00e9solution parall\u00e9le du probl\u00e9me SAT par d\u00e9composition structurelle. Master Thesis (in french), Universit\u00e9 Paul Verlaine-Metz (2007)","key":"27_CR23"},{"key":"27_CR24","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1006\/inco.1999.2860","volume":"162","author":"T.J. Park","year":"2000","unstructured":"Park, T.J., Van Gelder, A.: Partitioning Methods for Satisfiabilty Testing on Large Formulas. Information and Computation\u00a0162, 179\u2013184 (2000)","journal-title":"Information and Computation"},{"unstructured":"Parkes, A.J.: Exploiting Solutions Clusters for Coarse-Grained Distributed Search. In: Workshop on Dist. Constraints Reasoning, IJCAI 2001 (2001)","key":"27_CR25"},{"key":"27_CR26","volume-title":"CRPC Parallel Computing Handbook","author":"K. Schloegel","year":"2000","unstructured":"Schloegel, K., Karypis, G., Kumar, V.: Graph Partitioning for High Performance Scientific Simulations. In: Dongarra, J., et al. (eds.) CRPC Parallel Computing Handbook, Morgan Kauffmann, San Francisco (2000)"},{"key":"27_CR27","volume-title":"Parallel Combinatorial Optimization","author":"D. Singer","year":"2006","unstructured":"Singer, D.: Parallel Resolution of the Satisfiability Problem: a Survey. In: Talbi, E.-G. (ed.) Parallel Combinatorial Optimization, Wiley and Sons, Chichester (2006)"},{"unstructured":"Singer, D., Monnet, A.: A New Decomposition Scheme for Parallel Resolution of the Satisfiability Problem (SAT). In: 14th. RCRA 2007, Roma (2007)","key":"27_CR28"},{"key":"27_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11752578_46","volume-title":"Parallel Processing and Applied Mathematics","author":"D. Singer","year":"2006","unstructured":"Singer, D., Vagner, A.: Parallel Resolution of the Satisfiability Problem with OpenMP and MPI. In: Wyrzykowski, R., Dongarra, J., Meyer, N., Wa\u015bniewski, J. (eds.) PPAM 2005. LNCS, vol.\u00a03911, Springer, Heidelberg (2006)"},{"key":"27_CR30","volume-title":"MPI: the complete reference","author":"M. Snir","year":"1996","unstructured":"Snir, M., Otto, S.W., Huss-Lederman, S., Walker, D.W., Dongarra, J.: MPI: the complete reference. The MIT Press, Cambridge (1996)"}],"container-title":["Lecture Notes in Computer Science","Parallel Processing and Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-68111-3_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:08:42Z","timestamp":1605762522000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-68111-3_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540681052","9783540681113"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-68111-3_27","relation":{},"subject":[]}}