Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem

DOI10.1007/S10732-009-9123-5zbMath1205.90288OpenAlexW1985224354MaRDI QIDQ623311

Ana Paias, Luís Gouveia, Dushyant Sharma

Publication date: 14 February 2011

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-009-9123-5

zbMATH Keywords

heuristicshop-constrained treesexponential sized neighborhoodsrestricted dynamic programming

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Dynamic programming (90C39)

Related Items (6)

Hop constrained Steiner trees with multiple root nodes ⋮ Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem ⋮ Stabilizing branch‐and‐price for constrained tree problems ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ The hop-constrained minimum cost flow spanning tree problem with nonlinear costs: an ant colony optimization approach ⋮ The Minimum Cost Hop-and-root constrained forest in Wireless Sensor Networks

Cites Work

• Unnamed Item
• A survey of very large-scale neighborhood search techniques
• Multicommodity flow models for spanning trees with hop constraints
• The Steiner tree problem with hop constraints
• The 2-hop spanning tree problem
• Extended neighborhood: Definition and characterization
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem

This page was built for publication: Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem