A Lagrangian relaxation approach to the generalized minimum spanning tree problem

MaRDI QIDQ5308951zbMATH OpenFDO

Authors Petrica Pop

Publication date 8 October 2007

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)

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

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)