A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks

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

zbMATH Keywords

connected dominating setPTASwireless sensor networkunit ball graph

Mathematics Subject Classification ID

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