A greedy algorithm for the fault-tolerant connected dominating set in a general graph
From MaRDI portal
Publication:405692
DOI10.1007/s10878-013-9638-4zbMath1298.90122OpenAlexW2001733582MaRDI QIDQ405692
Kai Xing, Weili Wu, Zhao Zhang, Jiao Zhou
Publication date: 5 September 2014
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-013-9638-4
Related Items (12)
OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks ⋮ On approximating (connected) 2-edge dominating set by a tree ⋮ Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs ⋮ Further results on the total monochromatic connectivity of graphs ⋮ Fault-tolerant total domination via submodular function approximation ⋮ Construction of minimum edge-fault tolerant connected dominating set in a general graph ⋮ Computing Minimum k-Connected m-Fold Dominating Set in General Graphs ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ A greedy algorithm for the fault-tolerant outer-connected dominating set problem ⋮ Various bounds for liar's domination number ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
Cites Work
- Unnamed Item
- On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
- Design and analysis of approximation algorithms
- A greedy approximation for minimum connected dominating sets
- Minimum connected dominating sets and maximal independent sets in unit disk graphs
- On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
- A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
- Approximation algorithms for connected dominating sets
- On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
- On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
- MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
- ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
- Tighter Approximation Bounds for Minimum CDS in Wireless Ad Hoc Networks
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
This page was built for publication: A greedy algorithm for the fault-tolerant connected dominating set in a general graph