A note on the minimum label spanning tree

被引：40

作者：

Wan, YY ^{[1
]}

Chen, GL ^{[1
]}

Xu, YL ^{[1
]}

机构：

[1] Univ Sci & Technol China, Dept Comp Sci & Technol, Natl High Performance Comp Ctr, Hefei 230027, Peoples R China

来源：

INFORMATION PROCESSING LETTERS | 2002年 / 84卷 / 02期

关键词：

network design; NP-hard; approximation algorithms; spanning tree;

D O I：

10.1016/S0020-0190(02)00230-2

中图分类号：

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

学科分类号：

0812 ;

摘要：

We give a tight analysis of the greedy algorithm introduced by Krumke and Wirth for the minimum label spanning tree problem. The algorithm is shown to be a (In(n - 1) + 1)-approximation for any graph with n nodes (n > 1), which improves the known performance guarantee 2 In n + 1. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：99 / 101

页数：3