The minimum spanning tree constraint

Dooms, Gregoire;Katriel, Irit
(2006) 12th International Conference on Principles and Practice of Constraint Programming (CP 2006) — Location: Nantes(France) (25.September.2006)

Files

pdfdocument.pdf
  • Restricted Access
  • Adobe PDF
  • 500.78 KB
Request a copy

Details

Authors
  • Dooms, Gregoire
    Author
  • Katriel, Irit
    Author
Abstract
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Dooms, G., & Katriel, I. (2006). The minimum spanning tree constraint. Lecture Notes in Computer Science, 4204, 152-166. https://doi.org/10.1007/11889205_13 (Original work published 2006)