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

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

Zhao Zhang, Xiaofeng Gao, Du Ding-Zhu, 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

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 (13)

• 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 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
• A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph
• 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
• 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)