Name
Abstract | ||
|---|---|---|
The concepts of binary constraint satisfaction problems can be naturally generalized to the relation algebras of Tarski. The concept of path-consistency plays a central role. Algorithms for path-consistency can be implemented on matrices of relations and on matrices of elements from a relation algebra. We give an example of a 4-by-4 matrix of infinite relations on which on iterative local path-consistency algorithm terminates. We give a class of examples over a fixed finite algebra on which all iterative local algorithms, whether parallel or sequential, must take quadratic time. Specific relation algebras arising from interval constraint problems are also studied: the Interval Algebra, the Point Algebra, and the Containment Algebra. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1145/176584.176585 | J. ACM |
Keywords | Field | DocType |
iterative local path-consistency algorithm,binary constraint satisfaction problem,Point Algebra,infinite relation,path consistency,constraint matrices,Interval Algebra,specific relation,relation algebras,binary constraint problem,fixed finite algebra,Containment Algebra,constraint satisfaction problems,relations,relation algebra,interval constraint problem | Discrete mathematics,Algebra,Computer science,Constraint satisfaction problem,Binary constraint | Journal |
Volume | Issue | ISSN |
41 | 3 | 0004-5411 |
Citations | PageRank | References |
117 | 8.10 | 26 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter B. Ladkin | 1 | 626 | 90.51 |
| Roger D. Maddux | 2 | 310 | 33.14 |