A greedy algorithm for the fault-tolerant connected dominating set in a general graph

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

zbMATH Keywords

greedy algorithmnon-submodular potential function\(m\)-fold connected dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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