The “not-too-heavy spanning tree” constraint. (English) Zbl 1214.90121

Dooms, Grégoire; Katriel, Irit

Van Hentenryck, Pascal (ed.) et al., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. 4th international conference, CPAIOR 2007, Brussels, Belgium, May 23–26, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72396-7/pbk). Lecture Notes in Computer Science 4510, 59-70 (2007).

Summary: In this article, we develop filtering algorithms for the Weight-Bounded Spanning Tree (WBST\((G,T,I,W)\)) constraint, which is defined on undirected graph variables \(G\) and \(T\), a scalar variable \(I\) and a vector of scalar variables \(W\). It specifies that \(T\) is a spanning tree of \(G\) whose total weight is at most \(I\), where \(W\) is a vector of the edge weights.
For the entire collection see [Zbl 1120.68010].

MSC:

90C35

Programming involving graphs or networks