Modeling and solving the rooted distance-constrained minimum spanning tree problem

DOI10.1016/J.COR.2006.03.022zbMath1141.90031OpenAlexW1980866126MaRDI QIDQ2384910

Ana Paias, Dushyant Sharma, Luís Gouveia

Publication date: 10 October 2007

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2006.03.022

zbMATH Keywords

Lagrangian relaxationcolumn generationconstrained shortest path problemmodel reformulationDistance-constrained spanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Methods of reduced gradient type (90C52)

Related Items (14)

Layered graph approaches for combinatorial optimization problems ⋮ Optimal relay node placement in delay constrained wireless sensor network design ⋮ Hop constrained Steiner trees with multiple root nodes ⋮ Reload cost trees and network design ⋮ Stabilizing branch‐and‐price for constrained tree problems ⋮ An exact approach for the minimum-cost bounded-error calibration tree problem ⋮ Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem ⋮ A voltage drop limited decentralized electric power distribution network ⋮ On solving bi-objective constrained minimum spanning tree problems ⋮ New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints ⋮ Multiperiod location-routing with decoupled time scales ⋮ The Steiner tree problem with delays: a compact formulation and reduction procedures ⋮ A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints

Cites Work

• A Multicommodity Network-Flow Problem with Side Constraints on Paths Solved by Column Generation
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• Improved preprocessing, labeling and scaling algorithms for the Weight-Constrained Shortest Path Problem
• Validation of subgradient optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Modeling and solving the rooted distance-constrained minimum spanning tree problem