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

\(m\)-fold outer-connected dominating setgreedy algorithmpotential functionsubmodular

Mathematics Subject Classification ID

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

Review text

In this paper, the authors generalize the known outer-connected dominating set (OCSD) problem to the fault-tolerant OCDS problem. A vertex subset \(C\) of a graph \(G=(V,E)\) is an \(m\)-fold outer-connected dominating set (\(m\)-fold OCDS), if every vertex in \(V\setminus C\) has at least \(m\)-neighbors in \(C\) and the subgraph of \(G\) induced by \(V\setminus C\) is connected. The minimum \(m\)-fold OCDS problem of a graph \(G\) is to find an \(m\)-fold OCDS of minimum cardinality. The authors present a greedy algorithm for this problem and show that the approximation ratio is at most \(\alpha+1+\ln(\Delta+m +1)\), where \(\Delta\) is the maximum degree of the graph and \(\alpha\) is a positive number at most \(\Delta+m+1\).

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

• 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 a minimum outer-connected dominating set for the class of chordal graphs
• Computing Minimum k-Connected m-Fold Dominating Set in General Graphs
• Design and analysis of approximation algorithms
• Finding outer-connected dominating sets in interval graphs
• 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?)
• 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
• Fault-tolerant total domination via submodular function approximation
• A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'

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)