A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
From MaRDI portal
Publication:4446911
DOI10.1002/net.10097zbMath1031.05092OpenAlexW2022082910MaRDI QIDQ4446911
Weili Wu, Xiuzhen Cheng, Xiao Huang, Ding-Zhu Du, Deying Li
Publication date: 3 February 2004
Published in: Networks (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/11299/215507
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Minimum connected dominating sets and maximal independent sets in unit disk graphs ⋮ Bank supervision using the threshold-minimum dominating set ⋮ Approximating \(k\)-connected \(m\)-dominating sets ⋮ Minimum edge blocker dominating set problem ⋮ Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs ⋮ PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs ⋮ Two algorithms for minimum 2-connected \(r\)-hop dominating set ⋮ Approximate Aggregation for Tracking Quantiles in Wireless Sensor Networks ⋮ Unnamed Item ⋮ Efficient independent set approximation in unit disk graphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ PTAS for the minimum weighted dominating set in growth bounded graphs ⋮ Polynomial time approximation schemes for minimum disk cover problems ⋮ A greedy algorithm for the fault-tolerant connected dominating set in a general graph ⋮ Distributed connected dominating sets in unit square and disk graphs ⋮ A game theoretic approach for minimal connected dominating set ⋮ (6 + ε)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs ⋮ Algorithmic aspects of secure domination in unit disk graphs ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ On the Power of Lookahead in Greedy Scheme for Finding a Minimum CDS for Unit Disk Graphs ⋮ Polynomial time approximation scheme for \(t\)-latency bounded information propagation problem in wireless networks ⋮ Algorithms for the minimum weight \(k\)-fold (connected) dominating set problem ⋮ Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Complexity and lowers bounds for power edge set problem ⋮ A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs ⋮ 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 ⋮ Locating battery charging stations to facilitate almost shortest paths ⋮ Routing-efficient CDS construction in disk-containment graphs ⋮ On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs ⋮ Approximating k-Connected m-Dominating Sets ⋮ The wake up dominating set problem ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ The within-strip discrete unit disk cover problem ⋮ Connected dominating sets on dynamic geometric graphs ⋮ Capacitated domination problem ⋮ On connected domination in unit ball graphs ⋮ An exact algorithm for minimum CDS with shortest path constraint in wireless networks ⋮ Approximating minimum independent dominating sets in wireless networks ⋮ A greedy approximation for minimum connected dominating sets ⋮ Computing a tree having a small vertex cover ⋮ EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS ⋮ TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET ⋮ Unnamed Item ⋮ Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graphs ⋮ Improving construction for connected dominating set with Steiner tree in wireless sensor networks ⋮ Cellular Automata and Wireless Sensor Networks ⋮ 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 ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Some results for the two disjoint connected dominating sets problem ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Construction of strongly connected dominating sets in asymmetric multihop wireless networks ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ An efficient connected dominating set algorithm in WSNS based on the induced tree of the crossed cube ⋮ MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS ⋮ Efficient Local Search based on Dynamic Connectivity Maintenance for Minimum Connected Dominating Set ⋮ A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks ⋮ PTAS for connected vertex cover in unit disk graphs ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs ⋮ A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph ⋮ Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph ⋮ On connected dominating sets of restricted diameter
