A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs

DOI10.1007/s11590-009-0148-3zbMath1202.90042OpenAlexW1970098960MaRDI QIDQ1958631

Xiaofeng Gao, Weili Wu, Shiwei Zhu, Wei Wang, Zhao Zhang

Publication date: 4 October 2010

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-009-0148-3

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (3)

Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ A simpler PTAS for connected \(k\)-path vertex cover in homogeneous wireless sensor network

Cites Work

• Distributed routing algorithms for multi-hop ad hoc networks using \(d\)-hop connected \(d\)-dominating sets
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs
• Approximation and Online Algorithms

This page was built for publication: A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs