Toward a complexity classification of CSP through kernel width

Florian Richoux

Constraint Satisfaction Problems (CSP) constitute a universal formalism allowing to modelize a huge number of algorithmical and combinatorial problems, such as problems over graphs, databases, artificial intelligence,

Mots clés: Computational complexity; Constraint satisfaction problems; Kernel width

Domaines: Informatique [cs]

Florian Richoux. Toward a complexity classification of CSP through kernel width. Computer Science [cs]. Ecole Polytechnique X, 2009. English. ⟨NNT : ⟩. ⟨pastel-00005564⟩