On the minimum label spanning tree problem

被引：81

作者：

Krumke, SO ^{[1
]}

Wirth, HC ^{[1
]}

机构：

[1] Univ Wurzburg, Dept Comp Sci, D-97074 Wurzburg, Germany

来源：

INFORMATION PROCESSING LETTERS | 1998年 / 66卷 / 02期

关键词：

algorithms; NP-hardness; approximation algorithms; spanning tree;

D O I：

10.1016/S0020-0190(98)00034-9

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the Minimum Label Spanning Tree Problem. In this problem, we are given an undirected graph whose edges are labeled with colors. The goal is to find a spanning tree which uses as little different colors as possible. We present an approximation algorithm with logarithmic performance guarantee. On the other hand, our hardness results show that the problem cannot be approximated within a constant factor. (C) 1998 Elsevier Science B.V.

引用

页码：81 / 85

页数：5