Generalised arc consistency for the AllDifferent constraint: an empirical survey

DOI10.1016/j.artint.2008.10.006zbMath1184.68472MaRDI QIDQ2389692

Ian Miguel, Peter W. Nightingale, Ian Philip Gent

Publication date: 17 July 2009

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2008.10.006

zbMATH Keywords

constraint programming; constraint satisfaction problems; global constraints; alldifferent

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Related Items

The extended global cardinality constraint: an empirical survey, Implementing logical connectives in constraint programming, Propagation engine prototyping with a domain specific language, Redundant disequalities in the Latin square problem, Extending SMT solvers with support for finite domain \texttt{alldifferent} constraint

Uses Software

• CSPLib
• MINION
• Hopcroft-Karp

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Persistency in maximum cardinality bipartite matchings
• Watched Literals for Constraint Propagation in Minion
• The Problem of Compatible Representatives
• Depth-First Search and Linear Graph Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Recent Advances in Constraints
• Recent Advances in Constraints
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004