Article ID Journal Published Year Pages File Type
10524029 Operations Research Letters 2005 4 Pages PDF
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
Authors
, , ,