Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1042.68055
Wan, Yingyu; Chen, Guoliang; Xu, Yinlong
A note on the minimum label spanning tree. (English)
[J] Inf. Process. Lett. 84, No. 2, 99-101 (2002). ISSN 0020-0190

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 $(\ln(n-1)+1)$-approximation for any graph with $n$ nodes $(n>1),$ which improves the known performance guarantee $2\ln n+1.$.

MSC 2000:: *68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
68M10 Computer networks

Keywords: Network design; NP-hard; Approximation algorithms; Spanning tree

Cited in: Zbl 1124.05022

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]