The capacitated minimum spanning tree problem: On improved multistar constraints

DOI10.1016/J.EJOR.2003.10.021zbMATH Open1067.90141OpenAlexW2031476167MaRDI QIDQ1887863FDOQ1887863

Luis Gouveia, Maria João Lopes

Publication date: 22 November 2004

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2003.10.021

zbMATH Keywords

Lagrangean relaxationValid inequalitiesCapacitated treesMultistar constraintsSubset sum problems

Mathematics Subject Classification ID

Trees (05C05) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Validation of subgradient optimization
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
• Dynamic programming based heuristics for the topological design of local access networks
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• Experience with a Cutting Plane Algorithm for the Capacitated Spanning Tree Problem
• The complexity of the capacitated tree problem
• Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs

Cited In (17)

• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• A branch and bound algorithm for the capacitated minimum spanning tree problem
• A simple enhancement of the Esau–Williams heuristic for the capacitated minimum spanning tree problem
• Multi-exchange neighborhood structures for the capacitated minimum spanning tree problem
• A model for the capacitated, hop-constrained, per-packet wireless mesh network design problem
• Multistars and directed flow formulations
• Valid inequalities for non-unit demand capacitated spanning tree problems with flow costs
• Precedence-constrained arborescences
• A Branch-and-Bound Algorithm for Building Optimal Data Gathering Tree in Wireless Sensor Networks
• Parametric enhancements of the Esau–Williams heuristic for the capacitated minimum spanning tree problem
• A biased random-key genetic algorithm for the capacitated minimum spanning tree problem
• GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem
• The (K,k)-Capacitated Spanning Tree Problem
• A hybrid evolutionary algorithm for the capacitated minimum spanning tree problem
• A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem
• Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem
• A multicommodity network flow application for the capacitated minimal spanning tree problem

   Recommendations

• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem 👍 👎
• The capacitated minimal spanning tree problem: An experiment with a hop-indexed model 👍 👎
• The capacitated minimum spanning tree problem: revisiting hop-indexed formulations 👍 👎
• A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem. 👍 👎
• Heuristics for the multi-level capacitated minimum spanning tree problem 👍 👎

This page was built for publication: The capacitated minimum spanning tree problem: On improved multistar constraints

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