A mixed integer linear formulation for the minimum label spanning tree problem

被引：17

作者：

Captivo, M. Eugenia ^{[1
]}

Climaco, Joao C. N. ^{[2
,3
]}

Pascoal, Marta M. B. ^{[2
,4
]}

机构：

[1] Univ Lisbon, Fac Ciencias, Ctr Invest Operac, P-1749016 Lisbon, Portugal

[2] Inst Engn Sistemas & Comp Coimbra, P-3000033 Coimbra, Portugal

[3] Univ Coimbra, Fac Econ, P-3004512 Coimbra, Portugal

[4] Univ Coimbra, Dept Matemat, P-3001454 Coimbra, Portugal

来源：

COMPUTERS & OPERATIONS RESEARCH | 2009年 / 36卷 / 11期

关键词：

Spanning tree; Label; Color; Mixed integer formulation;

D O I：

10.1016/j.cor.2009.02.003

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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. (C) 2009 Elsevier Ltd. All rights reserved.

引用

页码：3082 / 3085

页数：4

共 10 条

[1]

Cerulli R, 2005, OPER RES COMPUT SCI, V29, P93

[2] The minimum labeling spanning trees [J].

Chang, RS ;

Leu, SJ .

INFORMATION PROCESSING LETTERS, 1997, 63 (05) :277-282

[3]

CONSOLI S, 2006, DEIOC4 U LAG

[4] On the minimum label spanning tree problem [J].

Krumke, SO ;

Wirth, HC .

INFORMATION PROCESSING LETTERS, 1998, 66 (02) :81-85

[5]

Kruskal J.B., 1956, Proc. Am. Math. Soc., V7, P48, DOI DOI 10.1090/S0002-9939-1956-0078686-7

[6] SHORTEST CONNECTION NETWORKS AND SOME GENERALIZATIONS [J].

PRIM, RC .

BELL SYSTEM TECHNICAL JOURNAL, 1957, 36 (06) :1389-1401

[7] A note on the minimum label spanning tree [J].

Wan, YY ;

Chen, GL ;

Xu, YL .

INFORMATION PROCESSING LETTERS, 2002, 84 (02) :99-101

[8]

XIONG Y, 2005, THESIS GRADUATE SCH

[9] Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem [J].

Xiong, YP ;

Golden, B ;

Wasil, E .

OPERATIONS RESEARCH LETTERS, 2005, 33 (01) :77-80

[10]

Xiong YP, 2008, OPER RES COMPUT SCI, P39

← 1 →