Constraint satisfaction problems: convexity makes AllDifferent constraints tractable

DOI10.1016/J.TCS.2012.11.038MaRDI QIDQ1939255zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael R. Fellows, Tobias Friedrich, Danny Hermelin, Nina Narodytska, Frances Rosamond

Publication date 4 March 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.11.038

zbMATH Keywords

AllDiff constraintscomplexityconstraint satisfaction problemsconvexityfixed parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Combinatorial optimization (90C27)

Recommendations

• Tractability in constraint satisfaction problems: a survey
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Complexity of conservative constraint satisfaction problems
• scientific article; zbMATH DE number 1008453
• On the Computational Complexity of Monotone Constraint Satisfaction Problems

Cited in

(5)

• The power of propagation: when GAC is enough
• Filtering algorithms for global chance constraints
• Solving finite-domain linear constraints in presence of the $\texttt{alldifferent}$
• Is constraint satisfaction over two variables always easy?
• scientific article; zbMATH DE number 2019637 (Why is no real title available?)

This page was built for publication: Constraint satisfaction problems: convexity makes AllDifferent constraints tractable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1939255)