Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem

被引：31

作者：

Xiong, YP

Golden, B ^{[1
]}

Wasil, E

机构：

[1] Univ Maryland, RH Smith Sch Business, College Pk, MD 20742 USA

[2] Univ Maryland, Dept Math, College Pk, MD 20742 USA

[3] American Univ, Kogod Sch Business, Washington, DC 20016 USA

来源：

OPERATIONS RESEARCH LETTERS | 2005年 / 33卷 / 01期

关键词：

algorithm; NP-hard; spanning trees; linear programming;

D O I：

10.1016/j.orl.2004.03.004

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we review recent work on the minimum labeling spanning tree problem and obtain a new worst-case ratio for the MVCA heuristic. We also present a family of graphs in which the worst-case ratio can be attained. This implies that the new ratio cannot be improved any further. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：77 / 80

页数：4

共 4 条

[1] Local search for the minimum label spanning tree problem with bounded color classes [J].