Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
475871 | Computers & Operations Research | 2009 | 4 Pages |
Abstract
In this paper we deal with the minimum label spanning tree problem. This is a relevant problem with applications such as telecommunication networks or electric networks, where each edge is assigned with a label (such as a color) and it is intended to determine a spanning tree with the minimum number of different labels. We introduce some mixed integer formulations for this problem and prove that one of their relaxations always gives the optimal value. Finally we present and discuss the results of computational experiments.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
M.Eugénia Captivo, João C.N. Clímaco, Marta M.B. Pascoal,