3.7.9. Alpha-acyclic constraint network(2)
Before defining alpha-acyclic constraint network(2) we first need to introduce the following notions:
The dual graph of a constraint network is defined in the following way: to each constraint of corresponds a vertex in the dual graph and if two constraints have a non-empty set of shared variables, there is an edge labelled between their corresponding vertices in the dual graph.
An edge in the dual graph of a constraint network is redundant if its variables are shared by every edge along an alternative path between the two end points [Dechter89].
If the subgraph resulting from the removal of the redundant edges of the dual graph is a tree the original constraint network is called -acyclic [Fagin83].
Alpha-acyclic constraint network(2) denotes an -acyclic constraint network such that, for any pair of constraints, the two sets of involved variables share at most two variables.