Using Lagrangian dual information to generate degree constrained spanning trees

DOI10.1016/j.dam.2005.06.011zbMath1120.90067OpenAlexW2034840381MaRDI QIDQ2489896

Rafael Andrade, Abilio Lucena, Nelson F. Maculan

Publication date: 28 April 2006

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2005.06.011

zbMATH Keywords

Lagrangian heuristicHeuristic improvement procedureInfeasibility preventionRestricted problem

Mathematics Subject Classification ID

Trees (05C05) Optimality conditions and duality in mathematical programming (90C46)

Related Items (13)

The salesman and the tree: the importance of search in CP ⋮ 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 ⋮ Degree-constrained \(k\)-minimum spanning tree problem ⋮ Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm ⋮ DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH ⋮ Exact solution approaches for the multi-period degree constrained minimum spanning tree problem ⋮ Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints ⋮ VNS and second order heuristics for the min-degree constrained minimum spanning tree problem ⋮ Design of capacitated degree constrained min-sum arborescence ⋮ Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Edge exchanges in the degree-constrained minimum spanning tree problem
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• Transitions in geometric minimum spanning trees
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• Minimum-weight degree-constrained spanning tree problem: Heuristics and implementation on an SIMD parallel machine
• A branch and cut method for the degree-constrained minimum spanning tree problem
• On two geometric problems related to the travelling salesman problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Topological design of centralized computer networks—formulations and algorithms
• A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
• A note on genetic algorithms for degree-constrained spanning tree problems
• Validation of subgradient optimization
• Low-Degree Spanning Trees of Small Weight
• Many birds with one stone
• Euclidean bounded-degree spanning tree ratios
• Matroids and the greedy algorithm
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Comparison of algorithms for the degree constrained minimum spanning tree

This page was built for publication: Using Lagrangian dual information to generate degree constrained spanning trees