An efficient algorithm for a class of constraint satisfaction problems

DOI10.1016/S0167-6377(01)00114-6zbMath1030.90112OpenAlexW2116267338MaRDI QIDQ1611994

Gerhard J. Woeginger

Publication date: 28 August 2002

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(01)00114-6

zbMATH Keywords

graph coloringsatisfiabilityefficient algorithmfeasibility checkinghorn formula

Mathematics Subject Classification ID

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

Related Items

Introduction to the Maximum Solution Problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Polynomial graph-colorings
• A generic arc-consistency algorithm and its specializations
• Constraints, consistency and closure
• Dynamic min-max problems
• The complexity of mean payoff games on graphs
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Closure properties of constraints
• Tractable constraints on ordered domains