A greedy algorithm for the fault-tolerant outer-connected dominating set problem

DOI10.1007/s10878-020-00668-zzbMath1477.05139OpenAlexW3105819400MaRDI QIDQ2025101

Yanyan Li

Publication date: 11 May 2021

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

Full work available at URL: https://doi.org/10.1007/s10878-020-00668-z

zbMATH Keywords

greedy algorithmsubmodularpotential function\(m\)-fold outer-connected dominating set

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the outer-connected domination in graphs
• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Finding outer-connected dominating sets in interval graphs
• Design and analysis of approximation algorithms
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• Paired-domination in graphs
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• On the complexity of the minimum outer-connected dominating set problem in graphs
• A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem

This page was built for publication: A greedy algorithm for the fault-tolerant outer-connected dominating set problem