Using Lagrangian dual information to generate degree constrained spanning trees

DOI10.1016/J.DAM.2005.06.011MaRDI QIDQ2489896zbMATH OpenOpenAlexFDO

Authors Rafael Andrade, Abilio Lucena, Nelson 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

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

Recommendations

• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• A Lagrangian relaxation approach to the generalized minimum spanning tree problem
• scientific article; zbMATH DE number 1086911
• A parallel Lagrangian relaxation algorithm for the min-degree constrained minimum spanning tree problem
• Spanning trees with constraints on the leaf degree
• scientific article; zbMATH DE number 1163716
• A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• The generalized dependency constrained spanning tree problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1021641 (Why is no real title available?)
• scientific article; zbMATH DE number 1054929 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• A branch and cut method for the degree-constrained minimum spanning tree problem
• A note on genetic algorithms for degree-constrained spanning tree problems
• Approximation algorithms for degree-constrained minimum-cost network-design problems
• Comparison of algorithms for the degree constrained minimum spanning tree
• Edge exchanges in the degree-constrained minimum spanning tree problem
• Euclidean bounded-degree spanning tree ratios
• Low-Degree Spanning Trees of Small Weight
• Many birds with one stone
• Matroids and the greedy algorithm
• Minimum-weight degree-constrained spanning tree problem: Heuristics and implementation on an SIMD parallel machine
• Network flows. Theory, algorithms, and applications.
• On the shortest spanning subtree of a graph and the traveling salesman problem
• On two geometric problems related to the travelling salesman problem
• Topological design of centralized computer networks—formulations and algorithms
• Transitions in geometric minimum spanning trees
• Validation of subgradient optimization
• Variable neighborhood search for the degree-constrained minimum spanning tree problem

Cited in

(17)

• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• NeuroPrim: an attention-based model for solving NP-hard spanning tree problems
• The salesman and the tree: the importance of search in CP
• 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
• Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• Degree-constrained \(k\)-minimum spanning tree problem
• Exact solution approaches for the multi-period degree constrained minimum spanning tree problem
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm
• A Lagrangian Decomposition/Evolutionary Algorithm Hybrid for the Knapsack Constrained Maximum Spanning Tree Problem
• Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
• LS(graph): a constraint-based local search for constraint optimization on trees and paths
• Min-degree constrained minimum spanning tree problem with fixed centrals and terminals: complexity, properties and formulations
• Design of capacitated degree constrained min-sum arborescence
• A Lagrangean-based decomposition approach for the link constrained Steiner tree problem

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

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