Congruence Distributivity Implies Bounded Width

DOI10.1137/080743238zbMath1205.68529OpenAlexW2082926001MaRDI QIDQ3586190

Libor Barto, Marcin Kozik

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080743238

zbMATH Keywords

constraint satisfaction problemcongruence distributive varietybounded widthlocal consistencyJónsson terms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Congruence modularity, congruence distributivity (08B10)

Related Items (5)

Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Deciding absorption in relational structures ⋮ Unnamed Item ⋮ Reflexive digraphs with near unanimity polymorphisms ⋮ Decidability of absorption in relational structures of bounded width.

This page was built for publication: Congruence Distributivity Implies Bounded Width