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

DOI10.1007/978-3-642-02026-1_4zbMath1246.90152OpenAlexW1570796947MaRDI QIDQ3637048

Peng-Jun Wan, Weili Wu, Xianyue Li, Yuexuan Wang, Feng Zou, Xiao-Hua Xu, Hongwei David 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 algorithmpolynomial-time approximation schemenode-weighted Steiner treeminimum weighted connected dominating set

Mathematics Subject Classification ID

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

Related Items (2)

A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints ⋮ Parameterized study of Steiner tree on unit disk graphs

This page was built for publication: A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs