Dichotomy for conservative digraphs
Speaker:
Alexandr Kazda, Charles University
Date and Time:
Tuesday, August 2, 2011 - 4:00pm to 4:30pm
Abstract:
We present an elementary proof that whenever G is a conservative digraphs such that CSP(G) is not NP-complete then CSP(G) can be solved by local consistency checking, ie. G has bounded width.
