A Lagrangian relaxation approach to the generalized minimum spanning tree problem

zbMATH Open1174.05332MaRDI QIDQ5308951FDOQ5308951

Authors: Petrica Pop 

Publication date: 8 October 2007

Recommendations

• Relaxation methods for the Generalized Minimum Spanning Tree problem
• A new relaxation method for the generalized minimum spanning tree problem
• New models of the generalized minimum spanning tree problem
• On the generalized minimum spanning tree problem
• Upper and lower bounding strategies for the generalized minimum spanning tree problem

zbMATH Keywords

minimum spanning treeNP-hardsubgradient methodLagrangian relaxationgeneralized minimum spanning tree problemGMSTP

Mathematics Subject Classification ID

Linear programming (90C05) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Integer programming (90C10)

Cited In (5)

• Polyhedral results, branch‐and‐cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
• Using Lagrangian dual information to generate degree constrained spanning trees
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• Relaxation methods for the Generalized Minimum Spanning Tree problem

This page was built for publication: A Lagrangian relaxation approach to the generalized minimum spanning tree problem

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