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

DOI10.1007/S11590-010-0208-8zbMATH Open1220.90149OpenAlexW2144308400MaRDI QIDQ537641FDOQ537641

Xiaofeng Gao, Xu Zhu, Ling Ding, Weili Wu, Wonjun 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

exact algorithmshortest pathCDS

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Title not available (Why is that?)
• Unit disk graphs
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• 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
• Approximations for Steiner trees with minimum number of Steiner points

Cited In (3)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q537641)