Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
PTAS for Minimum Connected Dominating Set with Routing Cost Constraint in Wireless Sensor Networks
verfasst von : Hongwei Du, Qiang Ye, Jioafei Zhong, Yuexuan Wang, Wonjun Lee, Haesun Park
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
To reduce routing cost and to improve road load balance, we study a problem of minimizing size of connected dominating set
D
under constraint that for any two nodes
u
and
v
, the routing cost through
D
is within a factor of
α
from the minimum, the cost of the shortest path between
u
and
v
. We show that for
α
≥ 5, this problem in unit disk graphs has a polynomial-time approximation scheme, that is, for any
ε
> 0, there is a polynomial-time (1 +
ε
)-approximation.