Constraint graph

Constraint graph
For a graph in electronic design automation, see Constraint graph (layout).

In constraint satisfaction research of artificial intelligence and operations research, constraint graphs and hypergraphs are used to represent relations among constraints in a constraint satisfaction problem.

Contents

Constraint hypergraph

The constraint hypergraph of a constraint satisfaction problem is a hypergraph in which hypervertices correspond to the variables and the hyperedges correspond to the constraints. Two hypervertices are in the same hyperedge if the two variables occur in the same constraint.[1]

Primal constraint graph

The primal constraint graph or simply primal graph (also the Gaifman graph) of a constraint satisfaction problem is the graph whose nodes are the variables of the problem and an edge joins a pair of variables if the two variables occur together in a constraint. [1]

The primal constraint graph is in fact the primal graph of the constraint hypergraph.

Dual constraint graph

The set of variables involved in a constraint is called the constraint scope. The dual constraint graph is the graph in which the vertices are all possible constraint scopes involved in the constraints of the problem and two vertices are connected by an edge if the corresponding scopes have common variables. [1]

References

  1. ^ a b c Handbook of Constraint Programming, by Francesca Rossi, Peter Van Beek, Toby Walsh (2006) ISBN 0444527265, p. 211, 212

Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Constraint graph (layout) — In some tasks of integrated circuit layout design a necessity arises to optimize placement of non overlapping objects in the plane. In general this problem is extremely hard, and to tackle it with computer algorithms, certain assumptions are made …   Wikipedia

  • Primal constraint graph — In constraint satisfaction, the primal constraint graph or simply primal graph (also the Gaifman graph) of a constraint satisfaction problem is the graph whose nodes are the variables of the problem and an edge joins a pair of variables if the… …   Wikipedia

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Constraint satisfaction dual problem — The dual problem is a reformulation of a constraint satisfaction problem expressing each constraint of the original problem as a variable. Dual problems only contain binary constraints, and are therefore solvable by algorithms tailored for such… …   Wikipedia

  • Constraint Composite Graph — The constraint composite graph is a node weighted undirected graph associated with a given combinatorial optimization problem posed as a weighted constraint satisfaction problem. Developed and introduced by Satish Kumar Thittamaranahalli (T. K.… …   Wikipedia

  • Constraint learning — In constraint satisfaction backtracking algorithms, constraint learning is a technique for improving efficiency. It works by recording new constraints whenever an inconsistency is found. This new constraint may reduce the search space, as future… …   Wikipedia

  • Constraint satisfaction — In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution to a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a vector of variables that… …   Wikipedia

  • Graph of desire — The graph of desire is a conceptual tool from the psychoanalytic theory of Jacques Lacan.HistoryLacan devised numerous quasi mathematical diagrams to represent the structure of the unconscious and its points of contact with empirical and mental… …   Wikipedia

  • Complexity of constraint satisfaction — The complexity of constraint satisfaction is the application of computational complexity theory on constraint satisfaction. It has mainly been studied for discriminating between tractable and intractable classes of constraint satisfaction… …   Wikipedia

  • Distributed constraint optimization — (DCOP or DisCOP) is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”