An exact algorithm for the node weighted Steiner tree problem

DOI10.1007/S10288-005-0081-YMaRDI QIDQ876575zbMATH OpenOpenAlexFDO

Authors Roberto Cordone, Marco Trubian

Publication date 19 April 2007

Published in 4OR (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10288-005-0081-y

zbMATH Keywords

Steiner problemrelax-and-cutprize collecting

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10) Integer programming (90C10) Network design and communication in computer systems (68M10)

Recommendations

• A strong lower bound for the Node Weighted Steiner Tree Problem
• The node-weighted steiner tree problem
• A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM
• Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees

Cited in

(10)

• The node-weighted steiner tree problem
• A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• An exact branch and bound algorithm for the Steiner Problem in Graphs
• A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM
• Algorithms for node-weighted Steiner tree and maximum-weight connected subgraph
• A node-based ILP formulation for the node-weighted dominating Steiner problem
• Solving the quadratic minimum spanning tree problem
• Solving Steiner trees: Recent advances, challenges, and perspectives
• scientific article; zbMATH DE number 913344 (Why is no real title available?)

This page was built for publication: An exact algorithm for the node weighted Steiner tree problem

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