Prize collecting Steiner trees with node degree dependent costs

DOI10.1016/j.cor.2010.04.016zbMath1231.90368OpenAlexW1988867041MaRDI QIDQ709134

Pedro Moura, Amaro de Sousa, Luís Gouveia

Publication date: 15 October 2010

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

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

zbMATH Keywords

valid inequalitiesSteiner treesdegree constraintsreformulation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Communication networks in operations research (90B18)

Related Items

Spanning trees with variable degree bounds ⋮ Single PON network design with unconstrained splitting stages ⋮ Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations ⋮ Enhancing discretized formulations: the knapsack reformulation and the star reformulation ⋮ A Lagrangean-based decomposition approach for the link constrained Steiner tree problem

Cites Work

• Unnamed Item
• 0-1 reformulations of the multicommodity capacitated network design problem
• Solving the variable size bin packing problem with discretized formulations
• On the capacitated concentrator location problem: a reformulation by discretization
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Multicommodity network design with discrete node costs
• Models and heuristics for the k ‐degree constrained minimum spanning tree problem with node‐degree costs
• Modeling and Solving the Two-Facility Capacitated Network Loading Problem
• Steiner Tree Problems With Profits