Bounds of MIN_NCC and MAX_NCC and filtering scheme for graph domain variables
Graph domain variables and constraints are an extension of constraint programming introduced by Dooms et al. This approach had been further investigated by Fages in its PhD thesis. On the other hand, Beldiceanu et al. presented a generic filtering scheme for global constraints based on graph properties. This scheme strongly relies on the computation of graph properties' bounds and can be used in the context of graph domain variables and constraints with a few adjustments. Bounds of MIN_NCC and MAX_NCC had been defined for the graph-based representation of global constraint for the path_with_loops graph class. In this note, we generalize those bounds for graph domain variables and for any graph class. We also provide a filtering scheme for any graph class and arbitrary bounds.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Collaborative Filtering with Graph Information: Consistency and Scalable Methods
Low rank matrix completion plays a fundamental role in collaborative filtering applications, the key idea being that the variables lie in a smaller subspace than the ambient space. Often, additional information about the…
Collaborative FilteringLow-Rank Matrix CompletionMatrix CompletionRecommendation SystemsBounds Arc Consistency for Weighted CSPs
The Weighted Constraint Satisfaction Problem (WCSP) framework allows representing and solving problems involving both hard constraints and cost functions. It has been applied to various problems, including resource alloc…
ARCSchedulingSolving finite-domain linear constraints in presence of the $\texttt{alldifferent}$
In this paper, we investigate the possibility of improvement of the widely-used filtering algorithm for the linear constraints in constraint satisfaction problems in the presence of the alldifferent constraints. In many …
Conjunctions of Among Constraints
Many existing global constraints can be encoded as a conjunction of among constraints. An among constraint holds if the number of the variables in its scope whose value belongs to a prespecified set, which we call its ra…
MAS: a multiplicative approximation scheme for probabilistic inference
We propose a multiplicative approximation scheme (MAS) for inference problems in graphical models, which can be applied to various inference algorithms. The method uses $\epsilon$-decompositions which decompose functions…