{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T17:16:35Z","timestamp":1771262195582,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s10601-019-09302-0","type":"journal-article","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T16:26:59Z","timestamp":1554481619000},"page":"234-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Encoding cardinality constraints using multiway merge selection networks"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4190-3033","authenticated-orcid":false,"given":"Micha\u0142","family":"Karpi\u0144ski","sequence":"first","affiliation":[]},{"given":"Marek","family":"Piotr\u00f3w","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"key":"9302_CR1","first-page":"80","volume-title":"Lecture Notes in Computer Science","author":"Ignasi Ab\u00edo","year":"2013","unstructured":"Ab\u00edo, I., Nieuwenhuis, R., Oliveras, A., Rodr\u00edguez-Carbonell, E. (2013). A Parametric Approach for Smaller and Better Encodings of Cardinality Constraints. In Schulte, C. (Ed.) Principles and practice of constraint programming - CP 2013, LNCS, (Vol. 8124 pp. 80\u201396). Heidelberg: Springer."},{"issue":"2","key":"9302_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10601-010-9105-0","volume":"16","author":"R As\u00edn","year":"2011","unstructured":"As\u00edn, R., Nieuwenhuis, R., Oliveras, A., Rodr\u00edguez-Carbonell, E. (2011). Cardinality networks: a theoretical and empirical study. Constraints, 16(2), 195\u2013221.","journal-title":"Constraints"},{"issue":"1","key":"9302_CR3","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10479-012-1081-x","volume":"218","author":"R As\u00edn","year":"2014","unstructured":"As\u00edn, R., & Nieuwenhuis, R. (2014). Curriculum-based course timetabling with SAT and MaxSAT. Annals of Operations Research, 218(1), 71\u201391.","journal-title":"Annals of Operations Research"},{"key":"9302_CR4","unstructured":"Aavani, A., Mitchell, D.G., Ternovska, E. (2013). New encoding for translating pseudo-Boolean constraints into SAT. In Frisch, A.M., Gregory, P. (eds.) SARA, AAAI."},{"key":"9302_CR5","doi-asserted-by":"crossref","first-page":"191","DOI":"10.3233\/SAT190021","volume":"2","author":"O Bailleux","year":"2006","unstructured":"Bailleux, O., Boufkhad, Y., Roussel, O. (2006). A translation of pseudo-boolean constraints to SAT, Journal on Satisfiability. Boolean Modeling and Computation, 2, 191\u2013200.","journal-title":"Boolean Modeling and Computation"},{"key":"9302_CR6","unstructured":"Batcher, K. E. (1968). Sorting networks and their applications. In Proceedings of the April 30\u2013May 2, 1968, spring joint computer conference, AFIPS \u201968 (Spring) (pp. 307\u2013314). New York: ACM."},{"key":"9302_CR7","unstructured":"Batcher, K. E., & Lee, D. (1995). A multiway merge sorting network. In: IEEE transactions on parallel and distributed systems, Vol. 6, No. 2, pp. 211\u2013215."},{"key":"9302_CR8","doi-asserted-by":"crossref","unstructured":"Biere, A., Cimatti, A., Clarke, E., Zhu, Y. (1999). Symbolic model checking without BDDs. In Proceedings of 5th international conference on tools and algorithms for the construction and analysis of systems (TACAS\u201999), LNCS, (Vol. 1579 pp. 193\u2013207). Heidelberg: Springer.","DOI":"10.21236\/ADA360973"},{"key":"9302_CR9","unstructured":"B\u00fcttner, M., & Rintanen, J. (2005). Satisfiability planning with constraints on the number of actions. In Proceedings of 15th International Conference on Automated Planning and Scheduling, pp. 292\u2013299."},{"key":"9302_CR10","unstructured":"Codish, M., & Zazon-Ivry, M. (2010). Pairwise cardinality networks. In Clarke, E., & Voronkov, A. (Eds.) Logic for programming, artificial intelligence, and reasoning, LNCS, (Vol. 6355 pp. 154\u2013172). Heidelberg: Springer."},{"key":"9302_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.3233\/SAT190014","volume":"2","author":"N E\u00e9n","year":"2006","unstructured":"E\u00e9n, N., & S\u00f6rensson, N. (2006). Translating Pseudo-Boolean Constraints into SAT. Journal on Satisfiability. Boolean Modeling and Computation, 2, 1\u201326.","journal-title":"Boolean Modeling and Computation"},{"key":"9302_CR12","unstructured":"Frisch, A.M., & Giannoros, P.A. (2010). SAT encodings of the At-Most-k constraint. Some Old, Some New, Some Fast, Some Slow. In Proc. of the 9th Int. workshop of constraint modelling and reformulation."},{"key":"9302_CR13","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.tcs.2017.09.036","volume":"707","author":"M Karpi\u0144ski","year":"2018","unstructured":"Karpi\u0144ski, M. (2018). Encoding cardinality constraints using standard encoding of generalized selection networks preserves arc-consistency. Theoretical Computer Science, 707, 77\u201381.","journal-title":"Theoretical Computer Science"},{"key":"9302_CR14","unstructured":"Karpi\u0144ski, M., & Piotr\u00f3w, M. (2018). Competitive sorter-based encoding of PB-constraints into SAT. To appear in the proceedings of Pragmatics of SAT 2018 Workshop."},{"key":"9302_CR15","unstructured":"Karpi\u0144ski, M., & Piotr\u00f3w, M. (2015). Smaller selection networks for cardinality constraints encoding. In Pesant, G. (Ed.) Principles and practice of constraint programming - CP 2015, LNCS, (Vol. 9255 pp. 210\u2013225): Springer International Publishing."},{"key":"9302_CR16","volume-title":"The art of computer programming, Volume 3: (2Nd Ed.) sorting and searching","author":"DE Knuth","year":"1998","unstructured":"Knuth, D. E. (1998). The art of computer programming, Volume 3: (2Nd Ed.) sorting and searching. Redwood City: Addison Wesley Longman Publishing Co., Inc."},{"key":"9302_CR17","unstructured":"Oh, C.H. (2016). Improving SAT solvers by exploiting empirical characteristics of CDCL. PHD thesis, New York University."},{"key":"9302_CR18","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1142\/S0129626492000337","volume":"2","author":"I Parberry","year":"1992","unstructured":"Parberry, I. (1992). The pairwise sorting network. Parallel Processing Letters, 2, 205\u2013211.","journal-title":"Parallel Processing Letters"},{"key":"9302_CR19","volume-title":"PBLib \u2013 A library for encoding pseudo-boolean constraints into CNF. Theory and applications of satisfiability testing \u2013 SAT 2015, LNCS, vol. 9340, pp. 9\u201316","author":"T Philipp","year":"2015","unstructured":"Philipp, T., & Steinke, P. (2015). PBLib \u2013 A library for encoding pseudo-boolean constraints into CNF. Theory and applications of satisfiability testing \u2013 SAT 2015, LNCS, vol. 9340, pp. 9\u201316. Berlin: Springer International Publishing."},{"key":"9302_CR20","doi-asserted-by":"publisher","first-page":"746","DOI":"10.1007\/978-3-642-04244-7_58","volume-title":"Principles and Practice of Constraint Programming - CP 2009","author":"Andreas Schutt","year":"2009","unstructured":"Schutt, A., Feydy, T., Stuckey, P., Wallace, M. (2009). Why cumulative decomposition is not as bad as it sounds. In Gent, I. (Ed.) Principles and practice of constraint programming - CP 2009, LNCS, (Vol. 5732 pp. 746\u2013761). Heidelberg: Springer."},{"key":"9302_CR21","doi-asserted-by":"crossref","unstructured":"Sinz, C. (2005). Towards an optimal CNF encoding of boolean cardinality constraints. In: Proc. of 11th International Conference on Principles and Practice of Constraint Programming, pp. 827\u2013831. Springer.","DOI":"10.1007\/11564751_73"},{"key":"9302_CR22","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0020-0190(98)00144-6","volume":"68","author":"JP Warners","year":"1998","unstructured":"Warners, J. P. (1998). A linear-time transformation of linear inequalities into conjunctive normal form. Information Processing Letters, 68, 63\u201369.","journal-title":"Information Processing Letters"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-019-09302-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-019-09302-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-019-09302-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T23:21:46Z","timestamp":1585956106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-019-09302-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,5]]},"references-count":22,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["9302"],"URL":"https:\/\/doi.org\/10.1007\/s10601-019-09302-0","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,5]]},"assertion":[{"value":"5 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}