A note on the minimum label spanning tree.

DOI10.1016/S0020-0190(02)00230-2MaRDI QIDQ1853118zbMATH OpenOpenAlexFDO

Authors Yingyu Wan, Yinlong Xu, Guoliang Chen

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00230-2

zbMATH Keywords

Approximation algorithmsNetwork designNP-hardSpanning tree

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Review text

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.\).

Recommendations

• On the minimum label spanning tree problem
• The minimum labeling spanning trees
• Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
• Local search for the minimum label spanning tree problem with bounded color classes.
• Approximation algorithms and hardness results for labeled connectivity problems

Cites work

• A threshold of ln n for approximating set cover
• On the minimum label spanning tree problem
• The minimum labeling spanning trees

Cited in

(20)

• The labeled maximum matching problem
• A mixed integer linear formulation for the minimum label spanning tree problem
• Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem
• The labeled perfect matching in bipartite graphs
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• A hybrid metaheuristic for the minimum labeling spanning tree problem
• Local search for the minimum label spanning tree problem with bounded color classes.
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
• The parameterized complexity of some minimum label problems
• Algorithms and complexity for a class of combinatorial optimization problems with labelling
• Variable neighbourhood search for the minimum labelling Steiner tree problem
• A polyhedral approach to the generalized minimum labeling spanning tree problem
• Least and most colored bases
• Approximation algorithms and hardness results for labeled connectivity problems
• On the bicriterion - minimal cost/minimal label - spanning tree problem
• Finding minimum label spanning trees using cross‐entropy method
• Solving the minimum label spanning tree problem by mathematical programming techniques
• Greedy approximation for the minimum connected dominating set with labeling
• Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems

This page was built for publication: A note on the minimum label spanning tree.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853118)