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

DOI10.1007/s10732-009-9123-5zbMath1205.90288MaRDI QIDQ623311

Luís Gouveia, Dushyant Sharma, Ana Paias

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

heuristics; hop-constrained trees; exponential sized neighborhoods; restricted dynamic programming

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

90C39: Dynamic programming

Related Items

Stabilizing branch‐and‐price for constrained tree problems, Hop constrained Steiner trees with multiple root nodes, Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem, 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