Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem

DOI10.1016/j.orl.2004.03.004zbMath1076.90050OpenAlexW1998751027MaRDI QIDQ1886801

Edward A. Wasil, Yupei Xiong, Bruce L. Golden

Publication date: 19 November 2004

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2004.03.004

zbMATH Keywords

AlgorithmLinear programmingNP-hardSpanning trees

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (15)

Greedy approximation for the minimum connected dominating set with labeling ⋮ On the bicriterion - minimal cost/minimal label - spanning tree problem ⋮ Finding minimum label spanning trees using cross‐entropy method ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Approximation and hardness results for label cut and related problems ⋮ The parameterized complexity of some minimum label problems ⋮ Solving the minimum label spanning tree problem by mathematical programming techniques ⋮ A hybrid metaheuristic for the minimum labeling spanning tree problem ⋮ Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems ⋮ Variable neighbourhood search for the minimum labelling Steiner tree problem ⋮ 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 ⋮ A polyhedral approach to the generalized minimum labeling spanning tree problem

Cites Work

• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Local search for the minimum label spanning tree problem with bounded color classes.
• A note on the minimum label spanning tree.

This page was built for publication: Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem