Constraint satisfaction problems: convexity makes AllDifferent constraints tractable

DOI10.1016/j.tcs.2012.11.038zbMath1257.68079OpenAlexW2042436180WikidataQ57359604 ScholiaQ57359604MaRDI QIDQ1939255

Danny Hermelin, Tobias Friedrich, Nina Narodytska, Michael R. Fellows, Frances A. 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

complexityconvexityfixed parameter tractabilityconstraint satisfaction problemsAllDiff constraints

Mathematics Subject Classification ID

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

Related Items

The power of propagation: when GAC is enough, Filtering algorithms for global chance constraints