{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,7]],"date-time":"2024-08-07T07:32:54Z","timestamp":1723015974415},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>The alldifferent constraint is an essential ingredient of most Constraints Satisfaction Problems (CSPs). It has been known that the generalized arc consistency (GAC) of alldifferent constraints can be reduced to the maximum matching problem in a value graph. The redundant edges, which do not appear in any maximum matching of the value graph, can and should be removed from the graph. The existing methods attempt to identify these redundant edges by computing the strongly connected components after finding a maximum matching for the graph. Here, we present a novel theorem for identification of the redundant edges. We show that some of the redundant edges can be immediately detected after finding a maximum matching. Based on this theoretical result, we present an efficient algorithm for processing alldifferent constraints. Experimental results on real problems show that our new algorithm significantly outperforms the-state-of-art approaches.<\/jats:p>","DOI":"10.24963\/ijcai.2018\/194","type":"proceedings-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T01:49:10Z","timestamp":1530755350000},"page":"1398-1403","source":"Crossref","is-referenced-by-count":4,"title":["A Fast Algorithm for Generalized Arc Consistency of the Alldifferent Constraint"],"prefix":"10.24963","author":[{"given":"Xizhe","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Northeastern University, Shenyang, Liaoning, China"},{"name":"Joint Laboratory of Artificial Intelligence and Precision Medicine of China Medical University and Northeastern University, Shenyang, Liaoning, China"}]},{"given":"Qian","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Northeastern University, Shenyang, Liaoning, China"}]},{"given":"Weixiong","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Math and Computer Science, Institute for Systems Biology, Jianghan University, Wuhan, China"},{"name":"Department of Computer Science and Engineering, Washington University, Saint Louis, Missouri, USA"}]}],"member":"10584","event":{"number":"27","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2018","name":"Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}","start":{"date-parts":[[2018,7,13]]},"theme":"Artificial Intelligence","location":"Stockholm, Sweden","end":{"date-parts":[[2018,7,19]]}},"container-title":["Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T01:50:42Z","timestamp":1530755442000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2018\/194"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2018\/194","relation":{},"subject":[],"published":{"date-parts":[[2018,7]]}}}