Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
DOI10.1007/978-3-540-85097-7_26zbMath1168.90635OpenAlexW1497398712MaRDI QIDQ5505666
Xianyue Li, Weili Wu, Feng Zou, Donghyun Kim
Publication date: 27 January 2009
Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-85097-7_26
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (5)
Cites Work
- Unnamed Item
- Unnamed Item
- A better constant-factor approximation for weighted dominating set in unit disk graph
- A fast algorithm for Steiner trees
- Improved methods for approximating node weighted Steiner trees and connected dominating sets.
- An 11/6-approximation algorithm for the network Steiner problem
- Improving construction for connected dominating set with Steiner tree in wireless sensor networks
- A threshold of ln n for approximating set cover
- The node-weighted steiner tree problem
- An integer linear programming approach to the steiner problem in graphs
- Improved Approximations for the Steiner Tree Problem
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Approximation algorithms for constrained for constrained node weighted steiner tree problems
- An algorithm for the steiner problem in graphs
- An algorithm for the steiner problem in graphs
- Approximations for Steiner trees with minimum number of Steiner points
This page was built for publication: Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
