Keywords:

Abstract:

Function filtering enhances dynamic programming methods working on a tree decomposition of the constraint graph. It is based on bounds for tuples: if the lower bound of tuple t is equal to or higher than a suitable upper bound, t can be discarded, decrementing the size of the message to travel in the tree decomposition. We present a new form of lower bound that tightens the lower bound of the original function filtering, so this new version –called two-sided function filtering– is more powerful. We provide experimental evidence of its benefits.

• Tagged
• XML
• BibTex