Using Lagrangian dual information to generate degree constrained spanning trees

DOI10.1016/J.DAM.2005.06.011zbMATH Open1120.90067OpenAlexW2034840381MaRDI QIDQ2489896FDOQ2489896

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

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

zbMATH Keywords

Lagrangian heuristicHeuristic improvement procedureInfeasibility preventionRestricted problem

Mathematics Subject Classification ID

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

Cites Work

• Network flows. Theory, algorithms, and applications.
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Title not available (Why is that?)
• 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
• Variable neighborhood search for the degree-constrained minimum spanning tree problem
• A branch and cut method for the degree-constrained minimum spanning tree problem
• Topological design of centralized computer networks—formulations and algorithms
• Title not available (Why is that?)
• A note on genetic algorithms for degree-constrained spanning tree problems
• Validation of subgradient optimization
• Matroids and the greedy algorithm
• Many birds with one stone
• Transitions in geometric minimum spanning trees
• On two geometric problems related to the travelling salesman problem
• 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
• Low-Degree Spanning Trees of Small Weight
• Euclidean bounded-degree spanning tree ratios
• Minimum-weight degree-constrained spanning tree problem: Heuristics and implementation on an SIMD parallel machine
• Title not available (Why is that?)

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
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• The salesman and the tree: the importance of search in CP
• 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)