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

DOI10.1007/S10878-020-00668-ZMaRDI QIDQ2025101zbMATH OpenOpenAlexFDO

Authors 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 algorithmpotential functionsubmodular\(m\)-fold outer-connected dominating set

Mathematics Subject Classification ID

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

Recommendations

• 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
• Construction of minimum edge-fault tolerant connected dominating set in a general graph
• A unified greedy approximation for several dominating set problems
• A greedy approximation for minimum connected dominating sets

Cites work

• scientific article; zbMATH DE number 5823716 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• 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
• Algorithm and hardness results for outer-connected dominating set in graphs
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Design and analysis of approximation algorithms
• Finding outer-connected dominating sets in interval graphs
• On constructing \(k\)-connected \(k\)-dominating set in wireless ad hoc and sensor networks
• On the complexity of the minimum outer-connected dominating set problem in graphs
• On the outer-connected domination in graphs
• Paired-domination in graphs
• The outer-connected domination number of a graph

Cited in

(4)

• A greedy algorithm for the fault-tolerant connected dominating set in a general graph
• Approximating fault-tolerant domination in general 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

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

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