Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1162.90575
Captivo, M.Eugénia; Cl{\'\i}maco, João C.N.; Pascoal, Marta M.B.
A mixed integer linear formulation for the minimum label spanning tree problem. (English)
[J] Comput. Oper. Res. 36, No. 11, 3082-3085 (2009). ISSN 0305-0548

Summary: 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.

MSC 2000:: *90C35 Network programming
90C11 Mixed integer programming
90B10 Flows in networks

Keywords: spanning tree; label; color; mixed integer formulation

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]