An exact algorithm for minimum CDS with shortest path constraint in wireless networks

DOI10.1007/s11590-010-0208-8zbMath1220.90149OpenAlexW2144308400MaRDI QIDQ537641

Xiaofeng Gao, Xu Zhu, Ling Ding, Weili Wu, Won Jun Lee

Publication date: 20 May 2011

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

Full work available at URL: https://doi.org/10.1007/s11590-010-0208-8

zbMATH Keywords

shortest pathexact algorithmCDS

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (3)

Minimum edge blocker dominating set problem ⋮ Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs ⋮ The probabilistic and reliable connected power dominating set problems

Cites Work

• Unnamed Item
• A greedy approximation for minimum connected dominating sets
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• Unit disk graphs
• Approximation algorithms for connected dominating sets
• Improving construction for connected dominating set with Steiner tree in wireless sensor networks
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Approximations for Steiner trees with minimum number of Steiner points

This page was built for publication: An exact algorithm for minimum CDS with shortest path constraint in wireless networks