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

Mathematics Subject Classification ID

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)

Wireless networking, dominating and packing ⋮ Approximations for node-weighted Steiner tree in unit disk graphs ⋮ Computing a tree having a small vertex cover ⋮ Algorithms for connected set cover problem and fault-tolerant connected set cover problem ⋮ Combinatorial optimization in system configuration design

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