Node-weighted Steiner tree approximation in unit disk graphs

DOI10.1007/s10878-009-9229-6zbMath1184.90146OpenAlexW2001352447MaRDI QIDQ849134

Weili Wu, Feng Zou, Xianyue Li, Suo-gang Gao

Publication date: 24 February 2010

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9229-6

zbMATH Keywords

approximation algorithmunit disk graphsnode-weighted Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (14)

Centrality measures for node-weighted networks via line graphs and the matrix exponential ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ Maximum lifetime connected coverage with two active-phase sensors ⋮ New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs ⋮ PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Approximating k-Connected m-Dominating Sets ⋮ On the hardness of full Steiner tree problems ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ Computing a tree having a small vertex cover ⋮ A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs ⋮ The price of connectivity for cycle transversals ⋮ Sensor Cover and Double Partition ⋮ On the clustered Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A better constant-factor approximation for weighted dominating set in unit disk graph
• A fast algorithm for Steiner trees
• An 11/6-approximation algorithm for the network Steiner problem
• 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
• An algorithm for the steiner problem in graphs
• Approximation and Online Algorithms
• An algorithm for the steiner problem in graphs
• Approximations for Steiner trees with minimum number of Steiner points

This page was built for publication: Node-weighted Steiner tree approximation in unit disk graphs