From Tetherless World Wiki
Citation: Berthe Y. Choueiry and Guevara Noubir. (1998) A Disjunctive Decomposition Scheme for Discrete Constraint Satisfaction Problems Using Complete No-Good Sets. In Knowledge Systems, AI Laboratory, August,1998.
| Publication inproceedings ( Edit )
|
| type | InProceedings
|
| bibtype | inproceedings
|
| Bibtex basics
|
| author | Berthe Y. Choueiry and Guevara Noubir
|
| title | A Disjunctive Decomposition Scheme for Discrete Constraint Satisfaction Problems Using Complete No-Good Sets
|
| booktitle | Knowledge Systems, AI Laboratory
|
| address | Stanford, CA, USA
|
| year | 1998
|
| month | August
|
| Bibtex more
|
| note | A previous version of this paper appeared in the Proceedings of FLAIRS'97.
|
| Access Paper
|
| abstract | In this paper, we introduce a new disjunctive decomposition scheme for discrete constraint satisfaction problems (CSPs). This strategy is based on first identifying complete no-goods in a graph derived from the microstructure of the CSP, then using these no-goods to decompose the initial CSP into subproblems that exclude these no-goods. This decomposition produces a partition of the solution space and is guaranteed to keep all solutions while reducing the total number of possibilities to be considered. We describe the strategy, study its properties, and identify the number of possibilities that are excluded at any decomposition step. We describe a practical application to which this strategy can be applied efficiently and compare our technique to some decomposition methods reported in the literature.
|
| KSL Technical Report ID: KSL-98-23
|
Facts about A Disjunctive Decomposition Scheme for Discrete Constraint Satisfaction Problems Using Complete No-Good SetsRDF feed
| Abstract | In this paper, we introduce a new disjunct … In this paper, we introduce a new disjunctive decomposition scheme for discrete constraint satisfaction problems (CSPs). This strategy is based on first identifying complete no-goods in a graph derived from the microstructure of the CSP, then using these no-goods to decompose the initial CSP into subproblems that exclude these no-goods. This decomposition produces a partition of the solution space and is guaranteed to keep all solutions while reducing the total number of possibilities to be considered. We describe the strategy, study its properties, and identify the number of possibilities that are excluded at any decomposition step. We describe a practical application to which this strategy can be applied efficiently and compare our technique to some decomposition methods reported in the literature. sition methods reported in the literature. |
| Address | Stanford, CA, USA + |
| Author | Berthe Y. Choueiry and Guevara Noubir + |
| Bibtype | inproceedings + |
| Booktitle | Knowledge Systems, AI Laboratory + |
| Has author | Berthe Y. Choueiry and Guevara Noubir + |
| Has identifier | KSL-98-23 + |
| Has publishing details | August,1998 + |
| Has title | A Disjunctive Decomposition Scheme for Discrete Constraint Satisfaction Problems Using Complete No-Good Sets + |
| Has where published | Knowledge Systems, AI Laboratory + |
| Has year | 1998 + |
| Ksl tr id | KSL-98-23 + |
| Month | August + |
| Note | A previous version of this paper appeared in the Proceedings of FLAIRS'97. + |
| Process note | NO + |
| Title | A Disjunctive Decomposition Scheme for Discrete Constraint Satisfaction Problems Using Complete No-Good Sets + |
| Year | 1998 + |
