the constraint satisfaction problem (CSP) and its quantified extensions, whether without (QCSP) or with disjunction (QCSP ), correspond naturally to the model checking problem for three increasingly stronger fragments...
详细信息
Preferences and uncertainty occur in many real-life problems. We are concerned withthe coexistence of preference and uncertainty in the same problem. In particular, we consider uncertainty, defined by the theory of p...
详细信息
the necessity of non-binary constraint satisfaction algorithms is increasing because many real problems are inherently non-binary. Considering overconstrained problems (and Partial Forward Checking as the solving algo...
详细信息
Computing lower bounds to the best-cost extension of a tuple is an ubiquous task in constraint optimization. A particular case of special interest is the computation of lower bounds to all singleton tuples, since it p...
详细信息
Traditionally, local consistency is defined as a relaxation of consistency which can be checked in polynomial time. It is accompanied by a corresponding "filtering" or "enforcing" algorithm that co...
详细信息
In recent years, many works have been carried out to solve over-constrained problems, and more specifically the Maximal constraint Satisfaction Problem (Max-CSP), where the goal is to minimize the number of constraint...
详细信息
the main advantage of constraintprogramming (CP) approaches for sequential pattern mining (SPM) is their modularity, which includes the ability to add new constraints (regular expressions, length restrictions, etc.)....
详细信息
Flow reasoning has been successfully used in CP for more than a decade. It was originally introduced by Régin in the well-known Alldifferent and Global Cardinality constraint (GCC) available in most of the CP sol...
详细信息
Bounded fractional hypertree width is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Fichte et al. (CP 2018) presented a robust and ...
详细信息
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating non-Hamiltonian edges from the associated graph. We prove a necessary condition for an edge t...
详细信息
ISBN:
(纸本)3540292381
We present an incomplete filtering algorithm for the circuit constraint. the filter removes redundant values by eliminating non-Hamiltonian edges from the associated graph. We prove a necessary condition for an edge to be Hamiltonian, which provides the basis for eliminating edges of a smaller graph defined on a separator of the original graph. the circuit constraint, circuit(y1,,yn}, where yj ∈ {1,,n}, is true if and only if for each j ∈ {1,, n}, y j is the successor of j in some permutation of 1 n and yj ∈ Dj, where Dj is the domain of variable j. On a graph of vertices 1,,n, the circuit constraint can be thought as defining a directed Hamiltonian cycle. Nodes of the graph represent the variables. A directed edge (i, j) exists if and only if j is in the domain of variable i. Moreover, elimination of an edge (i, j) from the graph means elimination of the value j from the domain of variable i. Withthis representation, the problem of domain reduction for the circuit constraint reduces to identifying and eliminating non-Hamiltonian edges on a digraph. In this paper, we present a recursive algorithm that eliminates non-Hamiltonian edges from the graph. A much smaller but denser multi-graph is constructed from a vertex separator S of the original graph by adding certain labelled edges to the subgraph induced by the separator. A directed edge (v, w) with label C is added if C is a connected component separated by S and (v, ci) and (cj, w) are edges of G for some pair of vertices ci, cj in C. We prove that edges that appear in no Hamiltonian cycle containing at least one edge of each component label in the constructed graph are non-Hamiltonian in the original graph. the condition that the constructed graph contains such a Hamiltonian cycle is viewed as a constraint. Global cardinality constraint with vertex degree constraints is a relaxation of this constraint. then by applying a filtering algorithm for the global cardinality constraint together with in and out-vertex de
暂无评论