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

DOI10.1007/S10898-008-9384-9zbMATH Open1189.90183OpenAlexW1988245406MaRDI QIDQ1037372FDOQ1037372

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

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

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)

Cites Work

• Unit disk graphs
• 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
• Approximation algorithms for connected dominating sets
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• A greedy approximation for minimum connected dominating sets
• MAXIMAL INDEPENDENT SET, WEAKLY-CONNECTED DOMINATING SET, AND INDUCED SPANNERS IN WIRELESS AD HOC NETWORKS
• On connected domination in unit ball graphs

Cited In (15)

• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• Performance analysis and improvement for the construction of MCDS problem in 3D space
• 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 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 greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
• Dimension zones of unit ball graphs
• Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem
• Wireless networking, dominating and packing
• A game theoretic approach for minimal connected dominating set
• A PTAS for minimum weighted connected vertex cover \(P_3\) problem in 3-dimensional wireless sensor networks
• A survey on variant domination problems in geometric intersection graphs
• A PTAS for weak minimum routing cost connected dominating set of unit disk graph
• The \(k\)-hop connected dominating set problem: approximation and hardness

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)