A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
From MaRDI portal
Publication:1037372
DOI10.1007/s10898-008-9384-9zbMath1189.90183OpenAlexW1988245406MaRDI QIDQ1037372
Zhao Zhang, Xiaofeng Gao, Ding-Zhu Du, Weili Wu
Publication date: 16 November 2009
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10898-008-9384-9
Programming involving graphs or networks (90C35) Communication networks in operations research (90B18)
Related Items (12)
The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ A game theoretic approach for minimal connected dominating set ⋮ Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem ⋮ Wireless networking, dominating and packing ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks ⋮ TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem ⋮ A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph
Cites Work
- On connected domination in unit ball graphs
- A greedy approximation for minimum connected dominating sets
- Unit disk graphs
- Approximation algorithms for connected dominating sets
- Improving construction for connected dominating set with Steiner tree in wireless sensor networks
- Approximation schemes for covering and packing problems in image processing and VLSI
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
This page was built for publication: A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
