Prize collecting Steiner trees with node degree dependent costs

DOI10.1016/J.COR.2010.04.016MaRDI QIDQ709134zbMATH OpenOpenAlexFDO

Authors Pedro Moura, Amaro de Sousa, Luis 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

Steiner treesvalid inequalitiesdegree constraintsreformulation

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic expedients for the prize collecting Steiner tree problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Generating lower bounds for the prize collecting Steiner problem in graphs
• Tight compact models and comparative analysis for the prize collecting Steiner tree problem
• scientific article; zbMATH DE number 1445375

Cites work

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

Cited in

(5)

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

This page was built for publication: Prize collecting Steiner trees with node degree dependent costs

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