User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

The minimum spanning tree constraint

Primary tabs

Dooms, Gregoire Katriel, Irit

The paper introduces the MST(G, T, W) constraint, which is specified on two graph variables G and T and a vector W of scalar variables. The constraint is satisfied if T is a minimum spanning tree of G, where the edge weights are specified by the entries of W. We develop algorithms that filter the domains of all variables to bound consistency.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès restreint
Publication date 2006
Language Anglais
Conference "12th International Conference on Principles and Practice of Constraint Programming (CP 2006)", Nantes(France) (Sep 25-29, 2006)
Journal information "Lecture Notes in Computer Science" - Vol. 4204, p. 152-166 (2006)
Peer reviewed yes
issn 0302-9743
e-issn 1611-3349
Publisher Springer-verlag Berlin (Berlin)
Affiliation UCL - Autre
Links
Bibliographic reference Dooms, Gregoire ; Katriel, Irit. The minimum spanning tree constraint.12th International Conference on Principles and Practice of Constraint Programming (CP 2006) (Nantes(France), Sep 25-29, 2006). In: Lecture Notes in Computer Science, Vol. 4204, p. 152-166 (2006)
Permanent URL http://hdl.handle.net/2078.1/59866