Approximation algorithms for constrained node weighted Steiner tree problems

DOI10.1145/380752.380826MaRDI QIDQ5175992zbMATH OpenOpenAlexFDO

Authors A. Moss, Yuval Rabani

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380826

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• scientific article; zbMATH DE number 1445375
• A better approximation algorithm for the budget prize collecting tree problem.

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(17)

• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• Approximation schemes for node-weighted geometric Steiner tree problems
• Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem
• The node-weighted steiner tree problem
• scientific article; zbMATH DE number 1796994 (Why is no real title available?)
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• scientific article; zbMATH DE number 913344 (Why is no real title available?)
• Bicriteria approximation tradeoff for the node-cost budget problem
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Balancing profits and costs on trees
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Approximating Steiner Networks with Node Weights
• Variations of the prize‐collecting Steiner tree problem
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Approximation algorithms for minimum weight partial connected set cover problem
• Approximating some network design problems with node costs

This page was built for publication: Approximation algorithms for constrained node weighted Steiner tree problems

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