Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Approximate Algorithm
Connected Dominating Set
Polynomial Time Approximation Scheme
steiner tree
steiner tree problem
Weight Function
Unit Disk Graph
Subscribe
Academic
Publications
A PTAS for NodeWeighted Steiner Tree in Unit Disk Graphs
A PTAS for NodeWeighted Steiner Tree in Unit Disk Graphs,10.1007/9783642020261_4,Xianyue Li,Xiaohua Xu,Feng Zou,Hongwei Du,Pengjun Wan,Yuexuan
Edit
A PTAS for NodeWeighted Steiner Tree in Unit Disk Graphs
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Xianyue Li
,
Xiaohua Xu
,
Feng Zou
,
Hongwei Du
,
Pengjun Wan
,
Yuexuan Wang
,
Weili Wu
The nodeweighted
Steiner tree problem
is a variation of classical Steiner minimum tree problem. Given a graph G = (V,E) with node
weight function
C:V→R + and a subset X of V, the nodeweighted
Steiner tree problem
is to find a
Steiner tree
for the set X such that its total weight is minimum. In this paper, we study this problem in unit disk graphs and present a (1+ε)approximation algorithm for any ε> 0, when the given set of vertices is clocal. As an application, we use nodeweighted
Steiner tree
to solve the nodeweighted
connected dominating set
problem in unit disk graphs and obtain a (5 + ε)approximation algorithm.
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 3648, 2009
DOI:
10.1007/9783642020261_4
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
References
(15)
Improved approximations for the Steiner tree problem
(
Citations: 100
)
Piotr Berman
,
Viswanathan Ramaiyer
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 325334, 1992
A 5+epsilonapproximation algorithm for minimum weighted dominating set in unit disk graph
(
Citations: 15
)
Decheng Dai
,
Changyuan Yu
Journal:
Theoretical Computer Science  TCS
, vol. 410, no. 810, pp. 756765, 2009
Computers and Intractability: A Guide to the Theory of NPCompleteness
(
Citations: 19196
)
Michael Randolph Garey
,
David S. Johnson
Conference:
Artificial Evolution  AE
, 1979
Approximation schemes for covering and packing problems in image processing and VLSI
(
Citations: 328
)
Dorit S. Hochbaum
,
Wolfgang Maass
Journal:
Journal of The ACM  JACM
, vol. 32, no. 1, pp. 130136, 1985
A 1.598 approximation algorithm for the Steiner problem in graphs
(
Citations: 28
)
Stefan Hougardy
,
Hans Jürgen Prömel
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 448453, 1999
Sort by:
Citations
(1)
PTAS for minimum weighted connected vertex cover problem with c local condition in unit disk graphs
Lidan Fan
,
Zhao Zhang
,
Wei Wang
Journal:
Journal of Combinatorial Optimization  JCO
, vol. 20, no. 2, pp. 111