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

DOI10.1007/S10878-013-9638-4MaRDI QIDQ405692zbMATH OpenOpenAlexFDO

Authors Jiao Zhou, Zhao Zhang, Weili Wu, Kai Xing

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

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• A greedy algorithm for the minimum 2-connected m-fold dominating set problem
• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• Construction of minimum edge-fault tolerant connected dominating set in a general graph
• Algorithms for minimum \(m\)-connected \(k\)-tuple dominating set problem
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs

Cites work

• A greedy approximation for minimum connected dominating sets
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• ANALYSIS ON THEORETICAL BOUNDS FOR APPROXIMATING DOMINATING SET PROBLEMS
• Approximation algorithms for connected dominating sets
• Design and analysis of approximation algorithms
• scientific article; zbMATH DE number 5764849 (Why is no real title available?)
• Minimum connected dominating sets and maximal independent sets in unit disk graphs
• MINIMUM CONNECTED r-HOP k-DOMINATING SET IN WIRELESS NETWORKS
• 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
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
• Tighter approximation bounds for minimum CDS in wireless ad hoc networks
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET

Cited in

(14)

• On approximating (connected) 2-edge dominating set by a tree
• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• Further results on the total monochromatic connectivity of graphs
• Construction of minimum edge-fault tolerant connected dominating set in a general graph
• OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
• Approximation for minimum strongly connected dominating and absorbing set with routing-cost constraint in disk digraphs
• False alarms in fault-tolerant dominating sets in graphs
• 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 minimum 2-connected m-fold dominating set problem
• Fault-tolerant total domination via submodular function approximation
• A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
• Various bounds for liar's domination number

This page was built for publication: A greedy algorithm for the fault-tolerant connected dominating set in a general graph

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