{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:14:56Z","timestamp":1743038096253,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031080104"},{"type":"electronic","value":"9783031080111"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-08011-1_26","type":"book-chapter","created":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T16:16:42Z","timestamp":1654791402000},"page":"390-407","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A Parallel Algorithm for\u00a0GAC Filtering of\u00a0the\u00a0Alldifferent Constraint"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6450-5620","authenticated-orcid":false,"given":"Wijnand","family":"Suijlen","sequence":"first","affiliation":[]},{"given":"F\u00e9lix","family":"de Framond","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4318-356X","authenticated-orcid":false,"given":"Arnaud","family":"Lallouet","sequence":"additional","affiliation":[]},{"given":"Antoine","family":"Petitet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"26_CR1","unstructured":"AMD: Memory population guidelines for AMD EPYC processors. Tech. Rep. 56301, revision 1.1, Advanced Micro Devices (2018)"},{"issue":"1","key":"26_CR2","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1109\/TPDS.2016.2546258","volume":"28","author":"A Azad","year":"2016","unstructured":"Azad, A., Bulu\u00e7, A., Pothen, A.: Computing maximum cardinality matchings in parallel on bipartite graphs via tree-grafting. IEEE Trans. Parallel Distrib. Syst. 28(1), 44\u201359 (2016). https:\/\/doi.org\/10.1109\/TPDS.2016.2546258","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-642-21311-3_6","volume-title":"Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems","author":"C Bessiere","year":"2011","unstructured":"Bessiere, C., Narodytska, N., Quimper, C.-G., Walsh, T.: The alldifferent constraint with precedences. In: Achterberg, T., Beck, J.C. (eds.) CPAIOR 2011. LNCS, vol. 6697, pp. 36\u201352. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-21311-3_6"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Bisseling, R.H.: Parallel Scientific Computing: A Structured Approach Using BSP. 2nd edn. Oxford University Press (2020)","DOI":"10.1093\/oso\/9780198788348.001.0001"},{"key":"26_CR5","doi-asserted-by":"publisher","unstructured":"Blelloch, G.E., Gu, Y., Shun, J., Sun, Y.: Parallelism in randomized incremental algorithms. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, p. 467\u2013478. SPAA 2016, Association for Computing Machinery, NY (2016). https:\/\/doi.org\/10.1145\/2935764.2935766","DOI":"10.1145\/2935764.2935766"},{"issue":"1\u20134","key":"26_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1145\/176454.176484","volume":"2","author":"P Briggs","year":"1993","unstructured":"Briggs, P., Torczon, L.: An efficient representation for sparse sets. ACM Lett. Program. Lang. Syst. 2(1\u20134), 59\u201369 (1993). https:\/\/doi.org\/10.1145\/176454.176484","journal-title":"ACM Lett. Program. Lang. Syst."},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/978-3-319-04132-2_11","volume-title":"Practical Aspects of Declarative Languages","author":"F Campeotto","year":"2014","unstructured":"Campeotto, F., Dal Pal\u00f9, A., Dovier, A., Fioretto, F., Pontelli, E.: Exploring the use of GPUs in constraint solving. In: Flatt, M., Guo, H.-F. (eds.) PADL 2014. LNCS, vol. 8324, pp. 152\u2013167. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-04132-2_11"},{"issue":"6","key":"26_CR8","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/BF01940880","volume":"15","author":"J Cheriyan","year":"1996","unstructured":"Cheriyan, J., Mehlhorn, K.: Algorithms for dense graphs and networks on the random access computer. Algorithmica 15(6), 521\u2013549 (1996). https:\/\/doi.org\/10.1007\/BF01940880","journal-title":"Algorithmica"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Erbas, C., Tanik, M.M.: Generating solutions to the N-queens problem using 2-circulants. Math. Mag. 68(5), 343\u2013356 (1995). http:\/\/www.jstor.org\/stable\/2690923","DOI":"10.1080\/0025570X.1995.11996355"},{"key":"26_CR10","unstructured":"Gecode Team: Gecode: generic constraint development environment (2019). http:\/\/www.gecode.org"},{"issue":"18","key":"26_CR11","doi-asserted-by":"publisher","first-page":"1973","DOI":"10.1016\/j.artint.2008.10.006","volume":"172","author":"IP Gent","year":"2008","unstructured":"Gent, I.P., Miguel, I., Nightingale, P.: Generalised arc consistency for the alldifferent constraint: an empirical survey. Artif. Intell. 172(18), 1973\u20132000 (2008). https:\/\/doi.org\/10.1016\/j.artint.2008.10.006","journal-title":"Artif. Intell."},{"issue":"5\u20136","key":"26_CR12","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1017\/S1471068418000340","volume":"18","author":"IP Gent","year":"2018","unstructured":"Gent, I.P., et al.: A review of literature on parallel constraint solving. Theory Pract. Logic Program. 18(5\u20136), 725\u2013758 (2018). https:\/\/doi.org\/10.1017\/S1471068418000340","journal-title":"Theory Pract. Logic Program."},{"issue":"2","key":"26_CR13","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969). https:\/\/doi.org\/10.1137\/0117039","journal-title":"SIAM J. Appl. Math."},{"issue":"3\u20134","key":"26_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/S0020-0190(00)00048-X","volume":"74","author":"L Granvilliers","year":"2000","unstructured":"Granvilliers, L., Hains, G.: A conservative scheme for parallel interval narrowing. Inf. Process. Lett. 74(3\u20134), 141\u2013146 (2000). https:\/\/doi.org\/10.1016\/S0020-0190(00)00048-X","journal-title":"Inf. Process. Lett."},{"issue":"3\u20134","key":"26_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1023\/A:1020594125144","volume":"7","author":"Y Hamadi","year":"2002","unstructured":"Hamadi, Y.: Optimal distributed arc-consistency. Constraints 7(3\u20134), 367\u2013385 (2002). https:\/\/doi.org\/10.1023\/A:1020594125144","journal-title":"Constraints"},{"key":"26_CR16","unstructured":"van Hoeve, W.-J.: The alldifferent constraint: a survey. CoRR cs.PL\/0105015 (2001). https:\/\/arxiv.org\/abs\/cs\/0105015"},{"key":"26_CR17","doi-asserted-by":"publisher","unstructured":"van Hoeve, W.-J., Katriel, I.: Global constraints. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2, pp. 169\u2013208. Elsevier (2006). https:\/\/doi.org\/10.1016\/S1574-6526(06)80010-6","DOI":"10.1016\/S1574-6526(06)80010-6"},{"key":"26_CR18","doi-asserted-by":"publisher","unstructured":"Hopcroft, J.E., Karp, R.M.: A n5\/2 algorithm for maximum matchings in bipartite. In: 12th Annual Symposium on Switching and Automata Theory, SWAT 1971, pp. 122\u2013125 (1971). https:\/\/doi.org\/10.1109\/SWAT.1971.1","DOI":"10.1109\/SWAT.1971.1"},{"key":"26_CR19","unstructured":"Huawei: Tecal RH2288H v2 rack server v100r002. Tech. rep., Huawei Technologies Co., Ltd. (2013), issue 01"},{"issue":"3","key":"26_CR20","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0004-3702(90)90009-O","volume":"45","author":"S Kasif","year":"1990","unstructured":"Kasif, S.: On the parallel complexity of discrete relaxation in constraint satisfaction networks. Artif. Intell. 45(3), 275\u2013286 (1990). https:\/\/doi.org\/10.1016\/0004-3702(90)90009-O","journal-title":"Artif. Intell."},{"key":"26_CR21","unstructured":"Van Kessel, P., Quimper, C.-G.: Filtering algorithms based on the word-ram model. In: Hoffmann, J., Selman, B. (eds.) Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 22\u201326 July 2012, Toronto, Ontario, AAAI Press (2012). http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI12\/paper\/view\/5135"},{"key":"26_CR22","unstructured":"Leconte, M.: A bounds-based reduction scheme for constraints of difference. In: Second International Workshop on Constraint-Based Reasoning, Key West, FL, p. 19\u201328 (1996)"},{"key":"26_CR23","unstructured":"L\u00f3pez-Ortiz, A., Quimper, C.-G., Tromp, J., van Beek, P.: A fast and simple algorithm for bounds consistency of the alldifferent constraint. In: Gottlob, G., Walsh, T. (eds.) IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, 9\u201315 August 2003, pp. 245\u2013250. Morgan Kaufmann (2003). http:\/\/ijcai.org\/Proceedings\/03\/Papers\/036.pdf"},{"key":"26_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/3-540-45349-0_23","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2000","author":"K Mehlhorn","year":"2000","unstructured":"Mehlhorn, K., Thiel, S.: Faster algorithms for bound-consistency of the sortedness and the alldifferent constraint. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 306\u2013319. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45349-0_23"},{"issue":"1\u20132","key":"26_CR25","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0167-6423(97)00012-9","volume":"30","author":"T Nguyen","year":"1998","unstructured":"Nguyen, T., Deville, Y.: A distributed arc-consistency algorithm. Sci. Comput. Program. 30(1\u20132), 227\u2013250 (1998). https:\/\/doi.org\/10.1016\/S0167-6423(97)00012-9","journal-title":"Sci. Comput. Program."},{"key":"26_CR26","unstructured":"Nightingale, P.: Are adjacency lists worthwhile in alldifferent. Tech. rep., Citeseer (2009)"},{"key":"26_CR27","unstructured":"Puget, J.: A fast algorithm for the bound consistency of alldiff constraints. In: Mostow, J., Rich, C. (eds.) Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 98, IAAI 98, 26\u201330 July 1998, Madison, Wisconsin, pp. 359\u2013366. AAAI Press\/The MIT Press (1998). http:\/\/www.aaai.org\/Library\/AAAI\/1998\/aaai98-051.php"},{"key":"26_CR28","unstructured":"R\u00e9gin, J.-C.: A filtering algorithm for constraints of difference in csps. In: Hayes-Roth, B., Korf, R.E. (eds.) Proceedings of the 12th National Conference on Artificial Intelligence, Seattle, WA, 31 July\u20134 August 1994, vol. 1, pp. 362\u2013367. AAAI Press\/The MIT Press (1994). http:\/\/www.aaai.org\/Library\/AAAI\/1994\/aaai94-055.php"},{"key":"26_CR29","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-319-63516-3_9","volume-title":"Handbook of Parallel Constraint Reasoning","author":"J-C R\u00e9gin","year":"2018","unstructured":"R\u00e9gin, J.-C., Malapert, A.: Parallel constraint programming. In: Handbook of Parallel Constraint Reasoning, pp. 337\u2013379. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-63516-3_9"},{"key":"26_CR30","unstructured":"Rolf, C.C., Kuchcinski, K.: Parallel consistency in constraint programming. In: Arabnia, H.R. (ed.) Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2009, Las Vegas, Nevada, 13\u201317 July 2009, 2 vols, pp. 638\u2013644. CSREA Press (2009)"},{"key":"26_CR31","unstructured":"Ruiz-Andino, A., Araujo, L., S\u00e1enz-P\u00e9rez, F., Ruz, J.J.: Parallel arc-consistency for functional constraints. In: Sagonas, K. (ed.) Proceedings of the International Workshop on Implementation Technology for Programming Languages Based on Logic, held in conjunction with the Joint International Conference and Symposium on Logic Programming, Manchester, UK, 20 June 1998, pp. 86\u2013100 (1998)"},{"key":"26_CR32","unstructured":"Suijlen, W.J.: BSPonMPI - BSPlib implementation on top MPI (2019). https:\/\/github.com\/wijnand-suijlen\/bsponmpi, version 1.1"},{"issue":"2","key":"26_CR33","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972). https:\/\/doi.org\/10.1137\/0201010","journal-title":"SIAM J. Comput."},{"issue":"3","key":"26_CR34","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/71.993206","volume":"13","author":"H Topcuoglu","year":"2002","unstructured":"Topcuoglu, H., Hariri, S., Wu, M.: Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. 13(3), 260\u2013274 (2002). https:\/\/doi.org\/10.1109\/71.993206","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"issue":"8","key":"26_CR35","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990)","journal-title":"Commun. ACM"},{"issue":"4","key":"26_CR36","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/s10766-013-0262-9","volume":"42","author":"AN Yzelman","year":"2013","unstructured":"Yzelman, A.N., Bisseling, R.H., Roose, D., Meerbergen, K.: MulticoreBSP for C: a high-performance library for shared-memory parallel programming. Int. J. Parallel Prog. 42(4), 619\u2013642 (2013). https:\/\/doi.org\/10.1007\/s10766-013-0262-9","journal-title":"Int. J. Parallel Prog."},{"key":"26_CR37","doi-asserted-by":"publisher","unstructured":"Zhang, X., Li, Q., Zhang, W.: A fast algorithm for generalized arc consistency of the alldifferent constraint. In: Lang, J. (ed.) Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, 13\u201319 July 2018, Stockholm, Sweden, pp. 1398\u20131403. ijcai.org (2018). https:\/\/doi.org\/10.24963\/ijcai.2018\/194","DOI":"10.24963\/ijcai.2018\/194"}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-08011-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T13:05:40Z","timestamp":1667912740000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-08011-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031080104","9783031080111"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-08011-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"10 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Los Angeles, CA","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":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/usc.edu\/cpaior-2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-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":"60","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":"28","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":"47% - 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","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)"}}]}}