Proceedings of ISP RAS


Theoretical and practical complexity estimates for local propagation methods in constraint-based programming applications.

V.A. Semenov, O.V. Sidyaka.

Abstract

The issues of efficiency and robustness of local propagation methods in conformity to constraint-based programming applications are discussed. Comparative analysis of known algorithms is given and new combined method is proposed. The method allows solving of wider classes of constraint problems for polynomial time. The results of computational experiments are presented to illustrate the method advantages over traditional algorithms.

Keywords

CLP programming, local propagation, computational complexity theory.

Edition

Proceedings of the Institute for System Programming, vol. 19, 2010, pp. 117-138.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Full text of the paper in pdf (in Russian) Back to the contents of the volume