Construction of minimum edge-fault tolerant connected dominating set in a general graph

DOI10.1007/S10878-023-00989-9MaRDI QIDQ2698012zbMATH OpenOpenAlexFDO

Authors Yaoyao Zhang, Zhao Zhang, Du Ding-Zhu

Publication date 14 April 2023

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-023-00989-9

zbMATH Keywords

approximation ratioconnected dominating setedge fault tolerancegreedy algorithm

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Recommendations

• A greedy algorithm for the minimum 2-connected m-fold dominating set problem
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• On approximation algorithms of \(k\)-connected \(m\)-dominating sets in disk graphs
• On minimum \(m\)-connected \(k\)-dominating set problem in unit disc graphs
• Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems

Cites work

• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• A greedy algorithm for the minimum 2-connected m-fold dominating set problem
• A note on two problems in connexion with graphs
• A polylogarithmic approximation algorithm for 2-edge-connected dominating set
• Approximation algorithms for connected dominating sets
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Connected dominating set. Theory and applications
• Graph theory
• Improved approximation algorithms for \(k\)-connected \(m\)-dominating set problems
• 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
• Optimal coverage in wireless sensor networks
• TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET

Cited in

(5)

• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set
• 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

This page was built for publication: Construction of minimum edge-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 Q2698012)