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

DOI10.1007/S10898-008-9384-9MaRDI QIDQ1037372zbMATH OpenOpenAlexFDO

Authors Zhao Zhang, Xiaofeng Gao, Weili Wu, Du Ding-Zhu

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

wireless sensor networkPTASconnected dominating setunit ball graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Communication networks in operations research (90B18)

Recommendations

• PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs
• On connected domination in unit ball graphs

Cites work

• A greedy approximation for minimum connected dominating sets
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximation algorithms for connected dominating sets
• Approximation schemes for covering and packing problems in image processing and VLSI
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• On connected domination in unit ball graphs
• Unit disk graphs

Cited in

(15)

• Performance analysis and improvement for the construction of MCDS problem in 3D space
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• A survey on variant domination problems in geometric intersection graphs
• Dimension zones of unit ball graphs
• Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
• Wireless networking, dominating and packing
• A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• A game theoretic approach for minimal connected dominating set
• The \(k\)-hop connected dominating set problem: approximation and hardness
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph

This page was built for publication: A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1037372)