Approximations for node-weighted Steiner tree in unit disk graphs

DOI10.1007/S11590-010-0194-XMaRDI QIDQ1958644zbMATH OpenOpenAlexFDO

Authors Peng-Jun Wan, Xianyue Li, Weili Wu, Xiao-Hua Xu, Yuexuan Wang, Hongwei Du, Feng Zou

Publication date 4 October 2010

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-010-0194-x

zbMATH Keywords

approximation algorithmnode-weighted Steiner treeunit-disk graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Node-weighted Steiner tree approximation in unit disk graphs
• A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs
• scientific article; zbMATH DE number 1302025
• The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights

Cites work

• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• An 11/6-approximation algorithm for the network Steiner problem
• Greedy approximations for minimum submodular cover with submodular cost
• Improved Approximations for the Steiner Tree Problem
• On two geometric problems related to the travelling salesman problem
• Thek-Steiner Ratio in Graphs
• Tighter Bounds for Graph Steiner Tree Approximation
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs

Cited in

(4)

• A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Node connectivity augmentation via iterative randomized rounding
• Node-weighted Steiner tree approximation in unit disk graphs

This page was built for publication: Approximations for node-weighted Steiner tree in unit disk graphs

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