A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM

DOI10.1142/S0217595908001791zbMath1163.90707OpenAlexW2150881926MaRDI QIDQ3526525

Roberto Cordone, Marco Trubian

Publication date: 25 September 2008

Published in: Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0217595908001791

zbMATH Keywords

knapsack constraintnode weighted Steiner tree problemrelax and cut algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks

Cites Work

• Strong lower bounds for the prize collecting Steiner problem in graphs
• Some generalizations of the steiner problem in graphs
• The node-weighted steiner tree problem
• An SST-based algorithm for the steiner problem in graphs
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• A strong lower bound for the Node Weighted Steiner Tree Problem
• A General Approximation Technique for Constrained Forest Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
• The Traveling-Salesman Problem and Minimum Spanning Trees