Anzeige
Erschienen in:
12.11.2020
A greedy algorithm for the fault-tolerant outer-connected dominating set problem
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2021
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
For a graph \(G=(V,E)\), a vertex set \(C\subseteq V\) is an m-fold outer-connected dominating set (m-fold OCDS) of G if every vertex in \(V\backslash C\) has at least m neighbors in C and the subgraph of G induced by \(V\backslash C\) is connected. In this paper, we present a greedy algorithm to compute an m-fold OCDS in general graphs, which returns a solution of size at most \(\alpha +1+\ln (\Delta +m+1)\) times that of a minimum m-fold OCDS, where \(\Delta \) is the maximum degree of the graph and \(\alpha \) is a positive number at most \(\Delta \)+m+1.