Models and heuristics for the k ‐degree constrained minimum spanning tree problem with node‐degree costs
From MaRDI portal
Publication:4648687
DOI10.1002/net.20445zbMath1251.68169MaRDI QIDQ4648687
Luís Gouveia, Mauricio C. de Souza, Christophe Duhamel, Pedro Moura
Publication date: 15 November 2012
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.20445
68Q25: Analysis of algorithms and problem complexity
90C10: Integer programming
90C05: Linear programming
68R10: Graph theory (including graph drawing) in computer science
Related Items
Spanning trees with variable degree bounds, Prize collecting Steiner trees with node degree dependent costs, Relations, models and a memetic approach for three degree-dependent spanning tree problems, Single PON network design with unconstrained splitting stages
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks
- Applying the pilot method to improve VNS and GRASP metaheuristics for the design of SDH/WDM networks
- 0-1 reformulations of the multicommodity capacitated network design problem
- Edge exchanges in the degree-constrained minimum spanning tree problem
- Variable neighborhood search for the degree-constrained minimum spanning tree problem
- Variable neighborhood search
- Greedy randomized adaptive search procedures
- Probability distribution of solution time in GRASP: an experimental investigation
- Solving the variable size bin packing problem with discretized formulations
- Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
- Reformulation by discretization: application to economic lot sizing
- TTT plots: a perl program to create time-to-target plots
- On the capacitated concentrator location problem: a reformulation by discretization
- A Comparison of Mixed-Integer Programming Models for Nonconvex Piecewise Linear Cost Minimization Problems
- Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs
- An annotated bibliography of GRASP-Part II: Applications
- Multicommodity network design with discrete node costs
- Lower and upper bounds for the degree-constrained minimum spanning tree problem
- An annotated bibliography of GRASP – Part I: Algorithms
- Variable Neighborhood Search
- A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
- Modeling and Solving the Two-Facility Capacitated Network Loading Problem