Article ID Journal Published Year Pages File Type
475871 Computers & Operations Research 2009 4 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computer Science (General)
Authors
, , ,