Automatically assigned DDC number: 005116

Manually assigned DDC number: 005116

Number of references: 0

Title: A Survey of Tractable Constraint Satisfaction Problems

Author:

Author:

Subject: Justin Pearson,Peter Jeavons A Survey of Tractable Constraint Satisfaction Problems

Description: In this report we discuss constraint satisfaction problems. These are problems in which values must be assigned to a collection of variables, subject to specified constraints. We focus specifically on problems in which the domain of possible values for each variable is finite. The report surveys the various conditions that have been shown to be sufficient to ensure tractability in these problems. These are broken down into three categories: ffl Conditions on the overall structure; ffl Conditions on the nature of the constraints; ffl Conditions on bounded pieces of the problem. 1 Introduction A constraint satisfaction problem is a way of expressing simultaneous requirements for values of variables. The study of constraint satisfaction problems was initiated by Montanari in 1974 [34], when he used them as a way of describing certain combinatorial problems arising in image-processing. It was quickly realised that the same general framework was applicable to a much wider class of probl...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1998-06-03

Pubyear: 1997

Format: ps

Identifier: http://citeseer.ist.psu.edu/140460.html

Source: http://www.docs.uu.se/~justin/survey.ps

Language: en

Rights: unrestricted

Graph

<?xml   version="1.0"   encoding="UTF-8"?>

<references_metadata>

      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="A   Survey   of   Tractable   Constraint   Satisfaction   Problems">

            <identifier   Org="ISBN:0120147734"   Paper_ID="SELF"   Extracted="0120147734"   DDC="537.5/6"   Normalized_DDC="53756"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0444527265"   Paper_ID="SELF"   Extracted="0444527265"   DDC="005.1/16"   Normalized_DDC="005116"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:0769510280"   Paper_ID="SELF"   Extracted="0769510280"   />

            <identifier   Org="ISBN:0897919963"   Paper_ID="SELF"   Extracted="0897919963"   />

            <identifier   Org="ISBN:140203816X"   Paper_ID="SELF"   Extracted="140203816X"   DDC="512"   Normalized_DDC="512"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:1558608117"   Paper_ID="SELF"   Extracted="1558608117"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:158113214X"   Paper_ID="SELF"   Extracted="158113214X"   DDC="005.3"   Normalized_DDC="0053"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:158113858X"   Paper_ID="SELF"   Extracted="158113858X"   />

            <identifier   Org="ISBN:1586038915"   Paper_ID="SELF"   Extracted="1586038915"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540004289"   Paper_ID="SELF"   Extracted="3540004289"   />

            <identifier   Org="ISBN:3540202021"   Paper_ID="SELF"   Extracted="3540202021"   DDC="005.1/1"   Normalized_DDC="00511"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540219374"   Paper_ID="SELF"   Extracted="3540219374"   DDC="006.3"   Normalized_DDC="0063"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540424962"   Paper_ID="SELF"   Extracted="3540424962"   DDC="004/.01/51"   Normalized_DDC="0040151"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540441204"   Paper_ID="SELF"   Extracted="3540441204"   DDC="005.1/1"   Normalized_DDC="00511"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540677151"   Paper_ID="SELF"   Extracted="3540677151"   DDC="005.1"   Normalized_DDC="0051"   Normalized_Weight="0.08333333333333333"   />

            <identifier   Org="ISBN:3540705740"   Paper_ID="SELF"   Extracted="3540705740"   />

            <identifier   Org="ISBN:3540730893"   Paper_ID="SELF"   Extracted="3540730893"   />

            <identifier   Org="ISBN:3540927999"   Paper_ID="SELF"   Extracted="3540927999"   />

            <identifier   Org="ISBN:887192228X"   Paper_ID="SELF"   Extracted="887192228X"   DDC="006"   Normalized_DDC="006"   Normalized_Weight="0.08333333333333333"   />

      </rec>

</references_metadata>