VNS and second order heuristics for the min-degree constrained minimum spanning tree problem

DOI10.1016/j.cor.2009.01.013zbMath1162.90577OpenAlexW2041944088MaRDI QIDQ1025243

Pedro Martins, Mauricio C. de Souza

Publication date: 18 June 2009

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2009.01.013

zbMATH Keywords

greedy heuristicsdegree constrained spanning tree problemsenhanced second order algorithmVNS algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm ⋮ A strong symmetric formulation for the min-degree constrained minimum spanning tree problem ⋮ Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations ⋮ Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations ⋮ A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem ⋮ The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm ⋮ New genetic algorithm approach for the MIN-degree constrained minimum spanning tree ⋮ Variable neighbourhood search: methods and applications ⋮ DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH ⋮ When diameter matters: parameterized approximation algorithms for bounded diameter minimum Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Looking ahead with the pilot method
• Enhanced second order algorithm applied to the capacitated minimum spanning tree problem
• Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem
• Applying the pilot method to improve VNS and GRASP metaheuristics for the design of SDH/WDM networks
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• Topological design of computer communication networks -- the overall design problem
• Design of survivable networks
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• Variable neighborhood search
• Using Lagrangian dual information to generate degree constrained spanning trees
• Variable neighborhood search for the vertex weighted \(k\)-cardinality tree problem
• The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs
• A New Class of Algorithms for Multipoint Network Optimization
• Variable Neighborhood Search
• Low-Degree Spanning Trees of Small Weight
• Comparison of algorithms for the degree constrained minimum spanning tree