A note on the minimum label spanning tree. (Q1853118)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on the minimum label spanning tree. |
scientific article |
Statements
A note on the minimum label spanning tree. (English)
0 references
21 January 2003
0 references
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.\).
0 references
Network design
0 references
NP-hard
0 references
Approximation algorithms
0 references
Spanning tree
0 references
