Simpler and incremental consistency checking and arc consistency filtering algorithms for the weighted spanning tree constraint. (English) Zbl 1142.68523

Perron, Laurent (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 5th international conference, CPAIOR 2008 Paris, France, May 20–23, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68154-0/pbk). Lecture Notes in Computer Science 5015, 233-247 (2008).
Summary: The weighted spanning tree contraint is defined from a set of variables \(X\) and a value \(K\). The variables \(X\) represent the nodes of a graph and the domain of a variable \(x \in X\) the neighbors of the node in the graph. In addition each pair (variable, value) is associated with a cost. This constraint states that the graph defined from the variables and the domains of the variables admits a spanning tree whose cost is less than \(K\). Efficient algorithms to compute a minimum spanning tree or to establish arc consistency of this constraint have been proposed. However, these algorithms are based on complex procedures that are rather difficult to understand and to implement. In this paper, we propose and detail simpler algorithms for checking the consistency of the constraint and for establishing arc consistency. In addition, we propose for the first time incremental algorithms for this constraint, that is algorithms that have been designed in order to be efficiently maintained during the search for solution.
For the entire collection see [Zbl 1136.68010].


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI