Worst-case behavior of the maximum vertex covering algorithm heuristic for the minimum labeling spanning tree problem

Worst-case behavior of the maximum vertex covering algorithm heuristic for the minimum labeling spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor2005707
Country: Netherlands
Volume: 33
Issue: 1
Start Page Number: 77
End Page Number: 80
Publication Date: Jan 2005
Journal: Operations Research Letters
Authors: , ,
Keywords: combinatorial analysis
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.

Reviews

Required fields are marked *. Your email address will not be published.