2004/07/16 by Willem Jan van Hoeve, van Hoeve, Willem Jan
Computer Science · #Advanced Database Systems and Queries #Constraint Satisfaction and Optimization #D.3.2 #D.3.3 #FOS: Computer and information sciences #G.2.2 #Logic, programming, and type systems #Programming Languages (cs.PL) #cs.PL
paper · pdf · doi:10.48550/arxiv.cs/0407043
11 pages, 1 figure
arxiv created 2004/07/16 · openalex publication_date 2004/07/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents an algorithm that achieves hyper-arc consistency for the soft alldifferent constraint. To this end, we prove and exploit the equivalence with a minimum-cost flow problem. Consistency of the constraint can be checked in O(nm) time, and hyper-arc consistency is achieved in O(m) time, where n is the number of variables involved and m is the sum of the cardinalities of the domains. It improves a previous method that did not ensure hyper-arc consistency.