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

greedy algorithm\(m\)-fold connected dominating setnon-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

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

Cited in

(14)

• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• False alarms in fault-tolerant dominating sets in graphs
• OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Various bounds for liar's domination number
• On approximating (connected) 2-edge dominating set by a tree
• On approximating (connected) 2-edge dominating set by a tree
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem
• 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
• A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'
• Construction of minimum edge-fault tolerant connected dominating set in a general graph
• Fault-tolerant total domination via submodular function approximation

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)