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

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

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

Recommendations

• Efficient distributed algorithms for topology control problem with shortest path constraints
• Polynomial-time approximation scheme for minimum connected dominating set under routing cost constraint in wireless sensor networks
• PTAS for minimum connected dominating set with routing cost constraint in wireless sensor networks
• Efficient algorithm for finding minimum connected dominating set in wireless sensor networks
• Approximation algorithms for connected dominating sets

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 (5)

• The probabilistic and reliable connected power dominating set problems
• Minimum edge blocker dominating set problem
• On connected dominating sets of restricted diameter
• Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
• Efficient distributed algorithms for topology control problem with shortest path constraints

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)