A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs

DOI10.1007/978-3-642-02026-1_4MaRDI QIDQ3637048zbMATH OpenOpenAlexFDO

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

Publication date 7 July 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02026-1_4

zbMATH Keywords

approximation algorithmminimum weighted connected dominating setnode-weighted Steiner treepolynomial-time approximation scheme

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Recommendations

• Node-weighted Steiner tree approximation in unit disk graphs
• Approximations for node-weighted Steiner tree in unit disk graphs
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Parameterized study of Steiner tree on unit disk graphs
• Parameterized Study of Steiner Tree on Unit Disk Graphs
• A strong lower bound for the Node Weighted Steiner Tree Problem
• An exact algorithm for the node weighted Steiner tree problem
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• The node-weighted steiner tree problem
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs

Cited in

(6)

• Approximations for node-weighted Steiner tree in unit disk graphs
• On full Steiner trees in unit disk graphs
• Parameterized study of Steiner tree on unit disk graphs
• A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Node-weighted Steiner tree approximation in unit disk graphs

This page was built for publication: A PTAS 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 Q3637048)