Local search for the minimum label spanning tree problem with bounded color classes.

DOI10.1016/S0167-6377(02)00241-9zbMath1046.90070OpenAlexW2156312014MaRDI QIDQ1811627

Jérôme Monnot, Tobias Brueggemann, Gerhard J. Woeginger

Publication date: 17 June 2003

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

Full work available at URL: https://doi.org/10.1016/s0167-6377(02)00241-9

zbMATH Keywords

ComplexityCombinatorial optimizationApproximation algorithmsLocal searchGraph algorithmsAPX-completeness

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Markov and semi-Markov decision processes (90C40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (24)

Comparison of metaheuristics for the k‐labeled spanning forest problem ⋮ Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem ⋮ On the hardness of labeled correlation clustering problem: a parameterized complexity view ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Approximation and hardness results for label cut and related problems ⋮ Labeled traveling salesman problems: complexity and approximation ⋮ The parameterized complexity of some minimum label problems ⋮ Local approximations for maximum partial subgraph problem. ⋮ Computational complexity analysis of the sensor location flow observability problem ⋮ Solving the minimum label spanning tree problem by mathematical programming techniques ⋮ A note on the clustered set covering problem ⋮ A hybrid metaheuristic for the minimum labeling spanning tree problem ⋮ The maximum labeled path problem ⋮ Algorithms and complexity results for labeled correlation clustering problem ⋮ Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ The complexity of bottleneck labeled graph problems ⋮ The labeled maximum matching problem ⋮ Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem ⋮ Solving the minimum labelling spanning tree problem using hybrid local search ⋮ The labeled perfect matching in bipartite graphs ⋮ A polyhedral approach to the generalized minimum labeling spanning tree problem ⋮ Approximate tradeoffs on weighted labeled matroids

Cites Work

• Local search, reducibility and approximability of NP-optimization problems
• Matching theory
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Face covers and the genus problem for apex graphs
• A note on the minimum label spanning tree.
• On Local Search for Weighted k-Set Packing
• A linear time approximation algorithm for multiprocessor scheduling
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Local search for the minimum label spanning tree problem with bounded color classes.