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

DOI10.1007/S10878-013-9638-4zbMATH Open1298.90122OpenAlexW2001733582MaRDI QIDQ405692FDOQ405692

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

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

zbMATH Keywords

greedy algorithm\(m\)-fold connected dominating setnon-submodular potential function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• 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
• Title not available (Why is that?)
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• A greedy approximation for minimum connected dominating sets
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• 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 PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• On the construction of \(k\)-connected \(m\)-dominating sets in wireless networks
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
• Design and analysis of approximation algorithms

Cited In (14)

• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• On Approximating (Connected) 2-Edge Dominating Set by a Tree
• 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
• 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'
• Fault-tolerant total domination via submodular function approximation
• Construction of minimum edge-fault tolerant connected dominating set in a general graph

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)