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

DOI10.1007/S10732-009-9123-5MaRDI QIDQ623311zbMATH OpenOpenAlexFDO

Authors Luis Gouveia, Ana Paias, 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

exponential sized neighborhoodsheuristicshop-constrained treesrestricted dynamic programming

Mathematics Subject Classification ID

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

Recommendations

• On formulations and methods for the hop-constrained minimum spanning tree problem
• New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs

Cites work

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

Cited in

(9)

• 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
• 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
• A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
• On solving bi-objective constrained minimum spanning tree problems
• Revisiting search methods for the bounded-diameter minimum spanning tree problem

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

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