An efficient algorithm for a class of constraint satisfaction problems

DOI10.1016/S0167-6377(01)00114-6MaRDI QIDQ1611994zbMATH OpenOpenAlexFDO

Authors 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, https://ris.utwente.nl/ws/files/6761127/Woeginger02efficient.pdf

zbMATH Keywords

efficient algorithmfeasibility checkinggraph coloringhorn formulasatisfiability

Mathematics Subject Classification ID

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

Recommendations

• On the efficient approximability of constraint satisfaction problems
• Automata, Languages and Programming
• Principles and Practice of Constraint Programming – CP 2004
• scientific article; zbMATH DE number 4162262
• Constraint satisfaction problems: Algorithms and applications
• scientific article; zbMATH DE number 6381632
• Near-optimal algorithms for maximum constraint satisfaction problems
• An LP-Designed Algorithm for Constraint Satisfaction
• Dynamic algorithms for classes of constraint satisfaction problems
• The approximability of constraint satisfaction problems

Cites work

• A generic arc-consistency algorithm and its specializations
• Closure properties of constraints
• Constraints, consistency and closure
• Dynamic min-max problems
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On the complexity of H-coloring
• Polynomial graph-colorings
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• The complexity of mean payoff games on graphs
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Tractable constraints on ordered domains

Cited in

(8)

• A combinatorial algorithm for Horn programs
• A CSP search algorithm with responsibility sets and kernels
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems
• A new algorithm for linear and integer feasibility in Horn constraints
• Adaptive Constraint Satisfaction: The Quickest First Principle
• scientific article; zbMATH DE number 4049150 (Why is no real title available?)
• Automata, Languages and Programming
• Introduction to the Maximum Solution Problem

This page was built for publication: An efficient algorithm for a class of constraint satisfaction problems

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