A PTAS for Weak Minimum Routing Cost Connected Dominating Set of Unit Disk Graph

DOI10.1007/978-1-4614-5131-0_9zbMath1308.90188OpenAlexW84359630MaRDI QIDQ5244687

Qinghai Liu, Zhao Zhang, Weili Wu, Yanmei Hong, Ding-Zhu Du

Publication date: 30 March 2015

Published in: Optimization, Simulation, and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-1-4614-5131-0_9

zbMATH Keywords

connected dominating setPTASunit disk graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs, An efficient connected dominating set algorithm in WSNS based on the induced tree of the crossed cube

Cites Work

• Unnamed Item
• On minimum submodular cover with submodular cost
• A greedy approximation for minimum connected dominating sets
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• Approximation algorithms for connected dominating sets
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• PTAS for Minimum Connected Dominating Set with Routing Cost Constraint in Wireless Sensor Networks
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• EFFICIENT DISTRIBUTED ALGORITHMS FOR TOPOLOGY CONTROL PROBLEM WITH SHORTEST PATH CONSTRAINTS